#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]});
vector<int>v;
int maxiSr=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);
maxiSr=max(maxiSr, maxi.fi);
mini={MAXV,0};
dfs(i, i);
int mid=mini.se;
v.pb(max(odl[mid][0], odl[mid][1]));
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if(v.size()>=2)
maxiSr=max(maxiSr, v[0]+v[1]+l);
return maxiSr;
}
/*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";
}*/
