Rudnick

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

using LL = long long;

vector < vector < int > > gr;
vector < int > pr;
vector < map < int, int > > weight;

const LL ADD = 1e16;
int n;

LL dfs(int v, int p) {
    LL ans = 0;
    if (v == n - 1) {
        ans += ADD;
    }
    pr[v] = p;
    if (p != -1) {
        ans += weight[v][p];
        ans += weight[p][v];
    }
    for (auto to: gr[v]) {
        if (to == p) {
            continue;
        }
        LL res = dfs(to, v);
        if (res > 0) {
            ans += res;
        }
    }
    return ans;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout.setf(std::ios_base::fixed);
    cout.precision(24);
    // freopen("input.txt", "r+", stdin);
    cin >> n;
    weight.resize(n);
    pr.resize(n, -1);
    gr.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int from, to;
        cin >> from >> to;
        from--; to--;
        int pw, qw;
        cin >> pw >> qw;
        weight[from][to] = pw;
        weight[to][from] = qw;
        gr[from].push_back(to);
        gr[to].push_back(from);
    }
    LL ans = dfs(0, -1);
    int v = n - 1;
    while (pr[v] != -1) {
        int from = pr[v];
        ans -= weight[v][from];
        v = from;
    }
    cout << ans - ADD;
    return 0;
}