#include <bits/stdc++.h>
#pragma optimize("Ofast")
#pragma target("avx2")
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll
const int MAX=1e5+15;
const ll inf=1e9;
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
int binpow(int a,int n){
if(!n)return 1;
if(n%2==1)return a*binpow(a,n-1);
int k=binpow(a,n/2);
return k*k;
}
#include "dreaming.h"
int n;
int tin[MAX],tout[MAX],timer;
int use[MAX];
int d[MAX];
int rev[MAX];
vector<pii> g[MAX];
vector<int> vec;
void dfs1(int v){
vec.pb(v);
use[v]=1;
for(auto to:g[v]){
if(!use[to.F])dfs1(to.F);
}
}
void dfs(int v,int p=-1){
tin[v]=++timer;
rev[timer]=v;
for(auto to:g[v]){
if(to.F!=p){
d[to.F]=d[v]+to.S;
dfs(to.F,v);
}
}
tout[v]=timer;
}
int t[4*MAX],add[4*MAX];
int C;
void build(int v,int tl,int tr){
add[v]=0;
if(tl==tr){
t[v]=d[rev[tl]];
return;
}
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=max(t[2*v],t[2*v+1]);
}
void push(int v){
add[2*v]+=add[v];
add[2*v+1]+=add[v];
t[2*v]+=add[v];
t[2*v+1]+=add[v];
add[v]=0;
}
void update(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
t[v]+=x;
add[v]+=x;
return;
}
int tm=(tl+tr)/2;
push(v);
update(2*v,tl,tm,l,r,x);
update(2*v+1,tm+1,tr,l,r,x);
t[v]=max(t[2*v],t[2*v+1]);
}
pii calc(int v,int p=-1){
int ans=t[1];
int ans1=t[1];
// cout<<v<<" "<<t[1]<<"\n";
for(auto to:g[v]){
if(to.F==p)continue;
update(1,1,C,tin[to.F],tout[to.F],-to.S);
update(1,1,C,1,tin[to.F]-1,to.S);
update(1,1,C,tout[to.F]+1,C,to.S);
pii bf=calc(to.F,v);
ans=max(ans,bf.F);
ans1=min(ans1,bf.S);
update(1,1,C,tin[to.F],tout[to.F],to.S);
update(1,1,C,1,tin[to.F]-1,-to.S);
update(1,1,C,tout[to.F]+1,C,-to.S);
}
// cout<<v<<" "<<ans<<" "<<t[1]<<"\n";
return {ans,ans1};
}
pii solve(vector<int> ver){
{
timer=0;
for(int i=1;i<=sz(ver);i++)rev[i]=0;
for(int x:ver)d[x]=0;
dfs(ver[0]);
}
C=sz(ver);
build(1,1,C);
pii res=calc(ver[0]);
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
// assert(M==N-2);
n=N;
for(int i=0;i<M;i++){
g[A[i]+1].pb({B[i]+1,T[i]});
g[B[i]+1].pb({A[i]+1,T[i]});
}
int mxD=0;
int ans=0;
vector<int> dep;
for(int i=1;i<=n;i++){
if(!use[i]){
dfs1(i);
pii bf=solve(vec);
dep.pb(bf.S);
mxD=max(mxD,bf.F);
vec.clear();
}
}
sort(all(dep));
if(sz(dep)>=2)ans=max(ans,dep.back()+dep[sz(dep)-2]+L);
if(sz(dep)>=3)ans=max(ans,dep[sz(dep)-2]+dep[sz(dep)-3]+L+L);
return max(mxD,ans);
}
