MINPATH

#include <bits/stdc++.h>
#define ll long long
#define root first
#define cost second
using namespace std;

const int N = 1005;
const int K = 25;

int n, height;
vector<pair<int, int> > graph[N];

ll up_cost[N][K], up_root[N][K];
int timer, time_in[N], time_out[N];

void init(int u, int p) {
    for (const auto &x : graph[u]) {
        int v = x.root;
        int c = x.cost;

        if(v == p) continue;

        up_root[v][0] = u;
        up_cost[v][0] = c;
        init(v, u);
    }
}

void DFS(int u, int p) {
    time_in[u] = ++timer;

    for (int i = 1; i <= height; i++) {
        int mid = up_root[u][i - 1];
        up_root[u][i] = up_root[mid][i - 1];
        up_cost[u][i] = up_cost[u][i - 1] + up_cost[mid][i - 1];
    }

    for (const auto &x : graph[u]) {
        int v = x.root;

        if (v != p) DFS(v, u);
    }

    time_out[u] = ++timer;
}

bool is_ancestor(int u, int v) {
    return time_in[u] <= time_in[v] && time_out[v] <= time_out[u];
}

ll find_LCA(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;

    for (int i = height; i >= 0; i--) {
        if (up_root[u][i] == 0) continue;

        if (!is_ancestor(up_root[u][i], v)) {
            u = up_root[u][i];
        }
    }

    return up_root[u][0];
}

ll find_sum(int p, int u) {
    ll sum = 0;

    for (int i = height; i >= 0; i--) {
        if (up_root[u][i] == 0) continue;

        if (is_ancestor(p, up_root[u][i])) {
            sum += up_cost[u][i];
            u = up_root[u][i];
        }
    }

    return sum;
}

void Print(int s, int t, int mid) {
    vector<int> ans1;
    for(int x = s; x != mid; x = up_root[x][0])
        ans1.push_back(x);
    for(int i = 0; i < ans1.size(); ++i)
        cout << ans1[i] << ' ';

    cout << mid << ' ';

    vector<int> ans2;
    for(int x = t; x != mid; x = up_root[x][0])
        ans2.push_back(x);
    for(int i = ans2.size() - 1; i >= 0; --i)
        cout << ans2[i] << ' ';
}

int main()
{
    //freopen("in.txt", "r", stdin);
    freopen("MINPATH.inp", "r", stdin);
    freopen("MINPATH.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    while(true) {
        int u, v, p, q;
        if(!(cin >> u >> v >> p >> q)) break;

        int w = p - q;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    height = ceil(log2(n)) + 1;

    init(1, 1);
    DFS(1, 1);

    ll ans = 1e9;
    ll mid = 0, s = 0, t = 0;

    for(int u = 1; u <= n; ++u) {
        for(int v = u + 1; v <= n; ++v) {
            int LCA = find_LCA(u, v);
            int sum = find_sum(u, v);

            if(ans >= sum)
                ans = sum, s = u, t = v, mid = LCA;
        }
    }

    cout << ans << '\n';
    Print(s, t, mid);

    return 0;
}