#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int INF = 1<<31-1;
const int MAXN = 1e5+7;
int xd[MAXN][3];
int ojc[MAXN];
int sum[MAXN];
bool visited[MAXN][3];
vector<int> v;
vector<pair<int,int> > g[MAXN];
int a,b,c,d,m,w,d1,curr,r;
void DFS1(int x,int f,int k){
visited[x][k]=1;
for(auto s:g[x]){
if(s.first==f) continue;
xd[s.first][k]=max(xd[s.first][k], xd[x][k]+s.second);
if(xd[s.first][k]>m){
m=xd[s.first][k];
d=s.first;
}
DFS1(s.first,x,k);
}
}
void DFS2(int x,int f,int k){
visited[x][k]=1;
ojc[x]=f;
for(auto s:g[x]){
if(s.first==f) continue;
xd[s.first][k]=max(xd[s.first][k], xd[x][k]+s.second);
sum[s.first]=sum[x]+s.second;
if(xd[s.first][k]>m){
m=xd[s.first][k];
d1=s.first;
}
DFS2(s.first,x,k);
}
}
int p=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=0;i<N;i++){
if(visited[i][0]==0){
m=0; d=i , d1=i;
DFS1(i,MAXN-1,0);
m=0;
DFS2(d,MAXN-1,1);
r=INF;
curr=d1;
p=max(p,sum[curr]);
while(curr!=MAXN-1){
if(max(sum[d1]-sum[curr], sum[curr])<r){
r=max(sum[d1]-sum[curr], sum[curr]);
w=curr;
}
curr=ojc[curr];
}
v.push_back(r);
}
}
if(v.size()==1){
return p;
}
else if(v.size()==2){
a=v[0];
b=v[1];
//cout<<a<<' '<<b<<' '<<L<<'\n';
return max(a+b+L,p);
}
else{
sort(v.begin(),v.end());
reverse(v.begin(), v.end());
a=v[0];
b=v[1];
c=v[2];
//cout<<a<<' '<<b<<' '<<c<<'\n';
return max({a+b+L,b+c+2*L,p});
}
}/*
int main(){
int A[100], B[100], T[100];
int n,m,l;
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)<<'\n';
}
*/
