#include <bits/stdc++.h>
#include "dreaming.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()
using namespace std;
const long long INF = 1e9;
const int MX=100005;
int n,m,l,dis[MX],go[MX];
vector<pii> adj[MX];
bool vis[MX];
pii DFS(int ver,int par,bool b){
vis[ver]=1;
pii ret;
ret={0,ver};
pii p;
for(auto i : adj[ver]){
if(i.F==par)C;
if(b)dis[i.F]=dis[ver]+i.S;
p=DFS(i.F,ver,b);
p.F+=i.S;
if(p.F>=ret.F){
ret.F=p.F;
ret.S=p.S;
}
}
// cout<<ver<<" "<<ret.F<<" "<<ret.S<<endl;
if(b)go[ver]=ret.F;
R ret;
}
pii dfs(int ver,int dia,int par){
if(dis[ver]+go[ver]!=dia)R {0,INF};
pii ret={dis[ver],go[ver]};
// cout<<ver<<" "<<dis[ver]<<" "<<go[ver]<<endl;
for(auto i : adj[ver]){
if(par==i.F)C;
pii p=dfs(i.F,dia,ver);
if(abs(p.F-p.S)<abs(ret.F-ret.S)){
ret=p;
}
}
R ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N,m=M,l=L;
for(int i=0;i<m;i++){
adj[A[i]].pb({B[i],T[i]});
adj[B[i]].pb({A[i],T[i]});
}
int mx1=0,mx2=0;
int ret=0;
vector<int>v;
for(int i=0;i<n;i++){
if(vis[i])C;
pii p=DFS(i,-1,0);
int x=p.S;
p=DFS(p.S,-1,1);
pii d=dfs(x,p.F,-1);
ret=max(ret,p.F);
// cout<<i<<" "<<p.F<<" "<<d.F<<" "<<d.S<<endl;
if(d.F<d.S)swap(d.F,d.S);
mx2=max(mx2,d.F);
v.pb(d.F);
if(mx1<mx2)swap(mx1,mx2);
}
sort(all(v));
reverse(all(v));
int b=N-M-1;
if(b>1){
ret=max(ret,2*L);
ret=max(ret,v[1]+v[2]+l+l);
}
ret=max(ret,mx1+mx2+(l*(b>0)));
return ret;
}
