#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> g[100001];int c[100001];int cc=1;int ld[100001];int rd[100001];
int cf=-1,cd=-1;int u[100001];
void mc(int i){
//cerr<<i<<endl;
c[i]=cc;
for(auto j:g[i])if(c[j.first]==0)mc(j.first);
}
void ffd(int i,int d){
if(d>cd){cd=d;cf=i;}
u[i]=1;
for(auto j:g[i])if(!u[j.first])ffd(j.first,d+j.second);
u[i]=0;
}
int ff(int i){
cf=cd=-1;
ffd(i,0);
return cf;
}
void fl(int i,int d){
//cerr<<"L "<<i<<' '<<d<<endl;
ld[i]=d;
for(auto j:g[i])if(ld[j.first]==-1)fl(j.first,d+j.second);
}
void fr(int i,int d){
//cerr<<"R "<<i<<' '<<d<<endl;
rd[i]=d;
for(auto j:g[i])if(rd[j.first]==-1)fr(j.first,d+j.second);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
//cerr<<n<<' '<<m<<endl;
//cerr<<"A"<<endl;
for(int i=0;i<m;i++){g[A[i]].push_back({B[i],T[i]});g[B[i]].push_back({A[i],T[i]});}
//cerr<<n<<' '<<m<<endl;
for(int i=0;i<n;i++)if(!c[i]){mc(i);cc++;}
cc--;//cerr<<cc<<endl;
//for(int i=0;i<n;i++)cerr<<c[i]<<' ';cerr<<endl;
int cr=1;
for(int i=0;i<n;i++)ld[i]=rd[i]=-1;
for(int i=0;i<n;i++){
if(c[i]!=cr)continue;
if(cr>cc)break;
int l=ff(i);int r=ff(l);
fl(l,0);fr(r,0);
cr++;
}
vector<int> s={-100000000};for(int i=1;i<=cc;i++)s.push_back(1e9+1);
for(int i=0;i<n;i++)s[c[i]]=min(s[c[i]],max(ld[i],rd[i]));
sort(s.begin(),s.end());//for(int i=1;i<=cc;i++)cout<<s[i]<<' ';cout<<endl;
if(cc==1)return s[1];
return max(s[cc]+s[cc-1]+L,s[cc-1]+s[cc-2]+2*L);
}
