#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pr = pair<int, int>;
#define pb push_back
const int INF = 1e9+7;
vector<vector<pr>> edge;
vector<int> dp, maxd;
int res = 0, curm;
int dfs1(int node, int par) {
int ans = 0;
for (auto [next, val] : edge[node]) {
if (next == par) continue;
int t = dfs1(next, node);
res = max(res, t + ans + val);
ans = max(ans, t + val);
}
return dp[node] = ans;
}
void dfs2(int node, int par, int parv) {
int sz = edge[node].size();
int ans = parv;
vector<int> pref(sz+1, 0), suff(sz+2, 0);
for (int i = 0; i < sz; i++) {
if (edge[node][i].first == par) pref[i+1] = pref[i];
else pref[i+1] = max(pref[i], dp[edge[node][i].first] + edge[node][i].second);
}
for (int i = sz-1; i >= 0; i--) {
if (edge[node][i].first == par) suff[i+1] = suff[i+2];
else suff[i+1] = max(suff[i+2], dp[edge[node][i].first] + edge[node][i].second);
}
ans = max(ans, pref[sz]);
for (int i = 0; i < sz; i++) {
if (edge[node][i].first == par) continue;
dfs2(edge[node][i].first, node, max({parv, pref[i], suff[i+2]}) + edge[node][i].second);
}
curm = min(curm, max(parv, pref[sz]));
return;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
edge.resize(N);
dp.assign(N, -1);
maxd.assign(N, -1);
for (int i = 0; i < M; i++) {
edge[A[i]].pb({B[i], T[i]});
edge[B[i]].pb({A[i], T[i]});
}
int mx = 0;
vector<int> part;
for (int i = 0; i < N; i++) {
if (dp[i] == -1) {
curm = INF;
dfs1(i, -1);
dfs2(i, -1, 0);
int t = curm;
part.pb(t);
}
}
sort(part.rbegin(), part.rend());
if (part.size() > 1)
res = max(res, part[0] + part[1] + L);
if (part.size() > 2)
res = max(res, part[1] + part[2] + L + L);
return res;
}
