#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10;
vector<pii> adj[MAXN];
int n, distante;
int dist[MAXN];
vector<vector<pii>> chains;
bool mrk_1[MAXN], mrk_2[MAXN];
int diam;
void dfs(int v, int c, bool save) {
mrk_1[v] = true;
if (save) {
mrk_2[v] = true;
chains.back().push_back({v, c});
}
if (dist[distante] < dist[v]) {
distante = v;
}
for (auto [w, nc]: adj[v]) {
if (mrk_1[w]) continue;
dist[w] = dist[v] + nc;
dfs(w, nc, save);
}
}
void find_chain(int v) {
for (int i = 0; i < n; i++) {
mrk_1[i] = false;
}
distante = v;
dist[v] = 0;
dfs(v, 0, 0);
for (int i = 0; i < n; i++) {
mrk_1[i] = false;
}
chains.push_back({});
dist[distante] = 0;
dfs(distante, 0, 1);
diam = max(dist[distante], diam);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
// subtask 3
assert(M == N - 2);
n = N;
for (int i = 0; i < M; i++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < n; i++) {
if (!mrk_2[i]) find_chain(i);
}
int resp = 0;
assert((int) chains.size() == 2);
for (auto &v: chains) {
int tot = 0;
for (pii &x: v) {
tot += x.second;
}
int l = 0, r = tot;
int best = tot;
for (pii &x: v) {
l += x.second;
r -= x.second;
best = min(best, max(l, r));
}
resp += best;
}
return max(diam, resp + L);
}
