#include <bits/stdc++.h>
#include"dreaming.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, MAXV=1e9+10;
int n, m, l, odl[MAX][2];
vector<pair<int,int>>g[MAX];
pair<int,int>maxi;
bool odw[MAX];
void dfso(int v, int oj, int x, int nr){
odl[v][nr]=x;
odw[v]=true;
maxi=max(maxi, {x, v});
for(auto s: g[v])
if(s.fi!=oj)
dfso(s.fi, v, x+s.se, nr);
}
pair<int,int>mini;
void dfs(int v, int oj){
mini=min(mini, {max(odl[v][0], odl[v][1]), v});
for(auto s: g[v])
if(s.fi!=oj)
dfs(s.fi,v);
}
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++)
g[a[i]].pb({b[i], t[i]}), g[b[i]].pb({a[i], t[i]});
int ls1=-1, ls2=-1, lmid=-1, dl=0, lmids1=0, lmids2=0;
for(int i=0; i<n; i++){
if(odw[i])
continue;
maxi={0,0};
dfso(i, i, 0, 0);
int s1=maxi.se;
maxi={0,0};
dfso(s1, s1, 0, 0);
int s2=maxi.se;
maxi={0,0};
dfso(s2, s2, 0, 1);
mini={MAXV,0};
dfs(i, i);
int mid=mini.se;
int mids1=odl[mid][0], mids2=odl[mid][1];
if(ls1==-1){
ls1=s1, ls2=s2, lmid=mid, dl=odl[s2][0], lmids1=mids1, lmids2=mids2;
continue;
}
if(dl<max(mids1, mids2)+max(lmids1, lmids2)+l){
dl=max(mids1, mids2)+max(lmids1, lmids2)+l;
int nmid, ns1, ns2, nmids1, nmids2;
if(mids1>mids2 && lmids1>lmids2){
ns1=s1, ns2=ls1;
if(max(mids1, lmids1+l)<max(lmids1, mids1+l))
nmid=mid, nmids1=mids1, nmids2=lmids1+l;
else
nmid=lmid, nmids1=mids1+l, nmids2=lmids1;
}
if(mids1>mids2 && lmids2>lmids1){
ns1=s1, ns2=ls2;
if(max(mids1, lmids2+l)<max(lmids2, mids1+l))
nmid=mid, nmids1=mids1, nmids2=lmids2+l;
else
nmid=lmid, nmids1=mids1+l, nmids2=lmids2;
}
if(mids2>mids1 && lmids1>lmids2){
ns1=s2, ns2=ls1;
if(max(mids2, lmids1+l)<max(lmids1, mids2+l))
nmid=mid, nmids1=mids2, nmids2=lmids1+l;
else
nmid=lmid, nmids1=mids2+l, nmids2=lmids1;
}
if(mids2>mids1 && lmids2>lmids1){
ns1=s2, ns2=ls2;
if(max(mids2, lmids2+l)<max(lmids2, mids2+l))
nmid=mid, nmids1=mids2, nmids2=lmids2+l;
else
nmid=lmid, nmids1=mids2+l, nmids2=lmids2;
}
lmid=nmid, lmids1=nmids1, lmids2=nmids2, ls1=ns1, ls2=ns2;
}
if(dl<odl[s2][0])
ls1=s1, ls2=s2, lmid=mid, dl=odl[s2][0], lmids1=mids1, lmids2=mids2;
///cout<<ls1<<" "<<ls2<<" "<<dl<<" "<<lmids1<<" "<<lmids2<<"\n";
}
return dl;
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int N, M, L;
cin>>N>>M>>L;
int A[M+2], B[M+2], T[M+2];
for(int i=0; i<M; i++)
cin>>A[i]>>B[i]>>T[i];
cout<<travelTime(N, M, L, A, B, T)<<"\n";
}
*/
