#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pii = pair<int,int>;
#define F first
#define S second
#define lc v<<1
#define rc v<<1|1
const int N = 1e5 + 10, inf = 1.05e9;
int n,m,f[N*4],lz[N*4],t,st[N],fn[N],fl[N],di,h[N];
pii mn;
vector<pii> adj[N],ans;
void build(int v, int l, int r){
lz[v]=0;
if(r-l==1){
f[v]=h[l];
return;
}
int m=(l+r)>>1;
build(lc,l,m);
build(rc,m,r);
f[v]=max(f[lc],f[rc]);
}
void shift(int v, int l, int r){
f[v]+=lz[v];
if(r-l>1){
lz[lc]+=lz[v];
lz[rc]+=lz[v];
}
lz[v]=0;
}
void upd(int v, int l, int r, int tl, int tr, int x){
shift(v,l,r);
if(tl>=r || l>=tr || tl>=tr) return;
if(l>=tl && r<=tr){
lz[v]=x;
return shift(v,l,r);
}
int m=(l+r)>>1;
upd(lc,l,m,tl,tr,x);
upd(rc,m,r,tl,tr,x);
f[v]=max(f[lc],f[rc]);
}
int get(int v, int l, int r, int tl, int tr){
shift(v,l,r);
if(tl>=r || l>=tr || tl>=tr) return 0;
if(l>=tl && r<=tr) return f[v];
int m=(l+r)>>1;
return max(get(lc,l,m,tl,tr),get(rc,m,r,tl,tr));
}
void dfs(int v){
st[v]=t;
fl[v]=1;
for(auto [u,w] : adj[v]){
if(fl[u]) continue;
h[++t]=h[st[v]]+w;
dfs(u);
}
fn[v]=t;
}
void sfd(int v, int p){
di=max(di,f[1]);
if(f[1]<mn.F) mn={f[1],v};
for(auto [u,w] : adj[v]){
if(u==p) continue;
upd(1,0,t+1,0,t+1,w);
upd(1,0,t+1,st[u],fn[u]+1,-2*w);
sfd(u,v);
upd(1,0,t+1,0,t+1,-w);
upd(1,0,t+1,st[u],fn[u]+1,2*w);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
m=M;
for(int i=0; i<m; i++){
adj[A[i]].pb({B[i],T[i]});
adj[B[i]].pb({A[i],T[i]});
}
for(int i=0; i<n; i++){
if(fl[i]) continue;
t=0;
mn={inf,-1};
dfs(i);
build(1,0,t+1);
sfd(i,-1);
ans.pb(mn);
}
sort(ans.begin(),ans.end(),greater<>());
int k = ans.size();
if(k==1) return di;
if(k==2) return max(di,ans[0].F+ans[1].F+L);
return max({di,ans[0].F+ans[1].F+L,ans[1].F+ans[2].F+2*L});
}
