#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));
}
}
int m = (int)br.size();
sort(br.begin(), br.end());
int res = 0;
for (int i = 0; i < m; i++)
res = max(res, br[i].first + br[i].second);
for (int i = 0; i < m - 1; i++) {
res = max(res, br[i].first + br[m - 1].first + L);
}
if (m >= 3) res = max(res, br[m - 3].first + br[m - 2].first + 2 * L);
return res;
}
