#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int mx[nx], mxr[nx], nxt=0, mx1=INT_MAX, mx2=INT_MAX, ans, cmx, cnt;
bool vs[nx];
vector<vector<pair<int, int>>> d(nx);
vector<int> b(nx), c;
void dfs(int u, int p)
{
vs[u]=1; c.push_back(u);
for (auto [v, w]:d[u])
{
if (v==p) continue;
dfs(v, u);
mx[u]=max(mx[u], mx[v]+w);
}
}
void dfs2(int u, int p)
{
vector<int> pf(d[u].size()+2), sf(d[u].size()+2);
pf[0]=mxr[u];
for (int i=d[u].size()-1; i>=0; i--)
{
sf[i+1]=sf[i+2];
if (d[u][i].first==p) continue;
sf[i+1]=max(sf[i+1], d[u][i].second+mx[d[u][i].first]);
}
for (int i=0; i<d[u].size(); i++)
{
pf[i+1]=pf[i];
if (d[u][i].first==p) continue;
pf[i+1]=max(pf[i+1], d[u][i].second+mx[d[u][i].first]);
mxr[d[u][i].first]=max(pf[i], sf[i+2])+d[u][i].second;
}
for (auto [v, w]:d[u]) if (v!=p) dfs2(v, u);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
if (N==1) return 0;
if (N==2&&M==1) return T[0];
if (N==2) return L;
for (int i=0; i<M; i++) d[A[i]].push_back({B[i], T[i]}), d[B[i]].push_back({A[i], T[i]});
for (int i=0; i<N; i++)
{
if (vs[i]) continue;
c.clear();
dfs(i, i); dfs2(i, i);
cmx=INT_MAX;
for (auto x:c) cmx=min(cmx, max(mx[x], mxr[x]));
b[cnt++]=cmx;
}
for (int i=0; i<N; i++) ans=max(ans, mx[i]+mxr[i]);
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
if (cnt==1) return max(ans, b[0]);
if (cnt==2) return max(ans, b[0]+b[1]+L);
return max(ans, max(b[0]+L+b[1], b[1]+2*L+b[2]));
}
