#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define MP make_pair
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pii>> e(N+2);
vector<int> meow;
int inf = 1.1e9;
vector<int> dis(N+2, inf);
vector<int> vis(N+2, 0), fa(N+2,0);
for (int i = 0; i < M; i++) {
e[A[i]].push_back(MP(B[i], T[i]));
e[B[i]].push_back(MP(A[i], T[i]));
}
int mx = 0, mxid, omax = 0;
auto dfs = [&](int i, int par, auto &&dfs) -> void {
vis[i] = 1;
fa[i] = par;
if (dis[i] > mx) mx = dis[i], mxid = i;
for (auto [j,w] : e[i]) if (j != par) {
dis[j] = dis[i] + w;
dfs(j, i, dfs);
}
return;
};
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
dis[i] = 0;
mx = 0, mxid = i;
dfs(i, i, dfs);
int rt = mxid;
dis[rt] = 0;
mx = 0, mxid = rt;
dfs(rt, rt, dfs);
omax = max(mx, omax);
vector<int> route;
int now = mxid;
while (true) {
route.push_back(now);
if (now == rt) break;
now = fa[now];
}
int ans = mx;
for (int j : route) ans = min(ans, max(mx-dis[j], dis[j]));
meow.push_back(ans);
}
if (meow.size() == 1) return omax;
else if (meow.size() == 2) {
return max(omax,meow[0] + meow[1] + L);
}
else {
sort(meow.begin(), meow.end());
reverse(meow.begin(), meow.end());
int ans = meow[0]+meow[1]+L;
ans = max(ans, meow[1]+meow[2]+L*2);
ans = max(ans, omax);
return ans;
}
}
