#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <bitset>#include <algorithm>using namespace std;const int N = 10100;const int INF = 1 << 30;struct edge {int v, vlen, vpow;edge(int v = 0, int vlen = 0, int vpow = 0) : v(v), vlen(vlen), vpow(vpow){}};vector<vector<edge> > g;int maxdis[2][N], maxpath[2][N], path[N];int dfs(int curr, int prev) {maxdis[0][curr] = maxdis[1][curr] = 0;for(vector<edge>::iterator i = g[curr].begin();i != g[curr].end();i++) {int u = i->v;if(u == prev) continue;int d = dfs(u, curr) + i->vlen;if(d > maxdis[0][curr]) swap(d, maxdis[0][curr]), swap(u, maxpath[0][curr]);if(d > maxdis[1][curr]) swap(d, maxdis[1][curr]), swap(u, maxpath[1][curr]);}return maxdis[0][curr];}void max_path(int curr, int prev, int path) {::path[curr] = max(path, maxdis[0][curr]);for(vector<edge>::iterator i = g[curr].begin();i != g[curr].end();i++) {int u = i->v;if(u == prev) continue;if(u == maxpath[0][curr]) {max_path(u, curr, max(path, maxdis[1][curr]) + i->vlen);} else {max_path(u, curr, max(path, maxdis[0][curr]) + i->vlen);}}};int dp[N];int DP(int root, int prev, int pree) {dp[root] = pree;int sum = 0;for(vector<edge>::iterator i = g[root].begin();i != g[root].end();i++) {int u = i->v;if(u == prev) continue;sum = max(sum, DP(u, root, i->vpow));}if(sum != 0) dp[root] = min(dp[root], sum);return dp[root];}int main() {int n;while(scanf("%d", &n) == 1) {g = vector<vector<edge> >(n);int u, v, l, p;for(int i = 1;i < n;i++) {scanf("%d %d %d %d", &u, &v, &l, &p);u--, v--;g[u].push_back(edge(v, l, p));g[v].push_back(edge(u, l, p));}dfs(0, -1);max_path(0, -1, 0);int root = min_element(path, path + n) - path;int res = DP(root, -1, INF);printf("%dn", res);}return 0;}
