#include"dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int N=1e5+5;
int n,m,l; bool vis[N];
vector<ii> adj[N],child[N];
int root[N],numRoot;
ll mxDia[N],miDia[N];
ll mx[N],ans[N],out[N],pre[N],suf[N];
void dfs(int u){
vis[u]=true;
for(auto [v,w]:adj[u]) if(!vis[v]){
child[u].eb(v,w);
dfs(v);
maxi(mx[u],mx[v]+w);
}
}
void reroot(int u){
ans[u]=max(mx[u],out[u]);
// cout<<u _ ans[u] _ out[u]<<'\n';
maxi(mxDia[numRoot],ans[u]);
mini(miDia[numRoot],ans[u]);
rep(i,sz(child[u])){
int v=child[u][i].fi, w=child[u][i].se;
pre[i]=mx[v]+w;
if(i>0) maxi(pre[i], pre[i-1]);
}
ford(i,sz(child[u])-1,0){
int v=child[u][i].fi, w=child[u][i].se;
suf[i]=mx[v]+w;
if(i<sz(child[u])-1) maxi(suf[i],suf[i+1]);
}
rep(i,sz(child[u])){
int v=child[u][i].fi, w=child[u][i].se;
out[v]=out[u]+w;
if(i>0) maxi(out[v],pre[i-1]+w);
if(i<sz(child[u])-1) maxi(out[v],suf[i+1]+w);
}
for(auto [v,w]:child[u]) reroot(v);
}
ll hi[3],res;
int solve(){
memset(miDia,0x3f,sizeof(miDia));
rep(i,n) if(!vis[i]){
root[numRoot]=i;
dfs(i);
reroot(i);
numRoot++;
}
rep(i,numRoot) maxi(res,mxDia[i]);
memset(hi,-0x3f,sizeof(hi));
rep(i,numRoot){
maxi(hi[2],miDia[i]);
if(hi[1]<hi[2]) swap(hi[1],hi[2]);
if(hi[0]<hi[1]) swap(hi[0],hi[1]);
}
maxi(res, max(hi[0]+hi[1]+l,hi[1]+hi[2]+2*l));
return res;
}
int travelTime(int NN, int MM, int LL, int AA[], int BB[], int TT[]){
n=NN,m=MM,l=LL;
rep(i,m){
int u=AA[i],v=BB[i],t=TT[i];
adj[u].eb(v,t);
adj[v].eb(u,t);
}
return solve();
}
//int32_t main(){
// #define task "test"
// if(fopen(task".inp","r")){
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// cin.tie(0)->sync_with_stdio(0);
//
// int tc=1; //cin>>tc;
// rep(i,tc){
// solve();
// }
//}
