#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
#define ll long long
vector<pii> g[111111];
int dis[111111],vis[111111],cendis[111111];
vector<int> diameter[111111];
int mxi=0,mxd=0,cntg=0,st,en,mxg1=-1,mxg2=-1,mxg3=-1,ans=0;
void dfs(int now,int p)
{
vis[now]=1;
if(dis[now]>mxd)
mxd=dis[now],mxi=now;
//vis[now]=1;
for(auto x:g[now])
{
if(x.f==p) continue;
dis[x.f]=dis[now]+x.s;
dfs(x.f,now);
}
}
bool diamake(int now,int prev,int en)
{
diameter[cntg].push_back(now);
if(now==en) return 1;
for(auto x:g[now])
{
if(x.f==prev) continue;
if(diamake(x.f,now,en)) return 1;
}
diameter[cntg].pop_back();
return 0;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
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]});
}
//for(int i=1;i<=N;i++) dis[i]=INT_MAX;
for(int i=0;i<N;i++)
{
if(vis[i]) continue;
cntg++;
//vis[i]=1;
mxi=-1,mxd=-1;
dis[i]=0;
dfs(i,-1);
st=mxi;
mxi=-1,mxd=-1;
dis[st]=0;
dfs(st,-1);
en=mxi;
ans=max(ans,mxd);
diamake(st,-1,en);
//disdia[cntg]=mxd;
cendis[cntg]=1e9;
//cout<<mxd<<'\n';
for(auto x:diameter[cntg]) cendis[cntg]=min(cendis[cntg],max(dis[x],mxd-dis[x]));
//cout<<cendis[cntg]<<'\n';
if(cendis[cntg]>=1e9)
cendis[cntg]=0;
if(mxg1==-1||cendis[cntg]>mxg1) mxg3=mxg2,mxg2=mxg1,mxg1=cendis[cntg];
else{
if(mxg2==-1||cendis[cntg]>mxg2) mxg3=mxg2,mxg2=cendis[cntg];
else
{ if(mxg3==-1||cendis[cntg]>mxg3) mxg3=cendis[cntg];
}
}
//cout<<st<<' '<<en<<'\n';
}
//cout<<mxg1<<' '<<mxg2<<' '<<mxg3<<'\n';
if(mxg3==-1) return max(ans,mxg1+mxg2+L);
return max({ans,mxg1+mxg2+L,mxg2+mxg3+2*L});
}
/*int main()
{
int n,m,l,a[111111],b[111111],t[111111];
cin>>n>>m>>l;
for(int i=0;i<m;i++)
cin>>a[i]>>b[i]>>t[i];
cout<<travelTime(n,m,l,a,b,t);
}*/
