#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<long long ,long long>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5;
vector<ii>adj[maxn+2];
bool vis[maxn+2];
ii mx[maxn+2];
void dfs(int cur,int par){
for(auto x : adj[cur]){
if(x.fir==par)continue;
dfs(x.fir,cur);
if(mx[x.fir].fir + x.sec>mx[cur].fir){
mx[cur].sec=mx[cur].fir;
mx[cur].fir=mx[x.fir].fir + x.sec;
}
else if(mx[x.fir].fir + x.sec>mx[cur].sec){
mx[cur].sec=mx[x.fir].fir + x.sec;
}
}
}
long long brp;
void reroot(int cur,int par,int jrk){
vis[cur]=true;
ii sblm=mx[cur];
if(cur!=par){
int baru=mx[par].fir+jrk;
if(mx[par].fir-jrk==mx[cur].fir){
baru=mx[par].sec+jrk;
}
if(mx[cur].fir<baru){
mx[cur].sec=mx[cur].fir;
mx[cur].fir=baru;
}
else if(mx[cur].sec<baru){
mx[cur].sec=baru;
}
}
brp=min(brp,mx[cur].fir);
for(auto x : adj[cur]){
if(x.fir==par)continue;
reroot(x.fir,cur,x.sec);
}
mx[cur]=sblm;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int q=0;q<m;q++){
adj[a[q]].pb({b[q],t[q]});
adj[b[q]].pb({a[q],t[q]});
}
vector<int>apa;
int ans=0;
for(int q=0;q<n;q++){
if(vis[q])continue;
dfs(q,q);
brp=1e18;
reroot(q,q,0);
apa.pb(brp);
ans=max(ans,(int)mx[q].fir+(int)mx[q].sec);
}
sort(apa.rbegin(),apa.rend());
if(apa.size()>1){
ans=max(ans,apa[0]+apa[1]+l);
}
if(apa.size()>2){
ans=max(ans,apa[2]+apa[1]+2*l);
}
return ans;
}
// signed main(){
// int n,m,l;
// cin>>n>>m>>l;
// int a[n],b[n],t[n];
// for(int q=0;q<m;q++){
// cin>>a[q]>>b[q]>>t[q];
// }
// cout<<travelTime(n,m,l,a,b,t)<<endl;
// }
