#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > graph[100000];
int cnt,opt,mx,ch[100000],D[100000];
void dist(int v, int d){
if(d>mx) opt=v,mx=d;
ch[v]=cnt,D[v]=d;
for(auto [u,c]: graph[v]){
if(ch[u]!=cnt) dist(u,d+c);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int i,u,v;
vector<int> d;
for(i=0;i<M;i++){
graph[A[i]].push_back({B[i],T[i]});
graph[B[i]].push_back({A[i],T[i]});
}
for(i=0;i<N;i++){
if(ch[i]) continue;
cnt++,mx=-1,dist(i,0);
u=opt;
cnt++,mx=-1,dist(u,0);
v=opt;
//printf("i=%d u=%d v=%d\n",i,u,v);
int mn=mx;
while(v!=u){
for(auto [v2,c]: graph[v]){
if(D[v2]==D[v]-c){
v=v2;
break;
}
}
mn=min(mn,max(D[v],mx-D[v]));
}
d.push_back(-mn);
}
sort(d.begin(),d.end());
assert(d.size()==N-M);
if(M==N-1) return mx;
if(M==N-2) return -d[0]-d[1]+L;
return max(-d[0]-d[1]+L,-d[1]-d[2]+2*L);
}
