#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
vector<pair<int, int>> g[N];
vector<bool> vis;
int nxt[N];
int w[N];
int calc(int s, int p) {
vis[s] = true;
int res = 0;
nxt[s] = s;
w[s] = 0;
for (auto [to, wt] : g[s]) if (to != p) {
int x = calc(to, s);
if (res < x + wt) {
res = x + wt;
nxt[s] = to;
w[s] = wt;
}
}
return res;
}
pair<int, int> find_center(int s) {
calc(s, s);
while (nxt[s] != s) s = nxt[s];
calc(s, s);
vector<int> arr;
while (nxt[s] != s) {
arr.push_back(w[s]);
s = nxt[s];
}
int sum = 0;
for (int c : arr) sum += c;
int mn = sum;
int cur = 0;
for (int i = 0; i < (int)arr.size(); i++) {
cur += arr[i];
if (max(cur, sum - cur) < mn) {
mn = max(cur, sum - cur);
}
}
pair<int, int> res = {mn, sum - mn};
if (res.first < res.second)
swap(res.first, res.second);
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vis.assign(N, false);
vector<pair<int, int>> br;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
br.push_back(find_center(i));
assert(br.back().first >= br.back().second);
}
}
auto merge = [&](pair<int, int> t1, pair<int, int> t2) -> pair<int, int> {
if (t1.first + t1.second < t2.first + t2.second)
swap(t1, t2);
if (t1.first + t1.second >= t1.first + t2.first + L)
return t1;
t1.first += L;
t1.second = t2.first;
if (t1.first > t1.second + L) {
t1.first -= L;
t1.second += L;
}
if (t1.first < t1.second)
swap(t1.first, t1.second);
return t1;
};
sort(br.begin(), br.end(), [&](pair<int, int> a, pair<int, int> b) {
return (a.first + a.second < b.first + b.second);
});
// for (auto c : br) {
// cout << '(' << c.first << ' ' << c.second << ')' << ' ';
// }
// cout << '\n';
for (int i = 0; i < (int)br.size() - 1; i++) {
br.back() = merge(br.back(), br[i]);
}
return br.back().first + br.back().second;
}
