#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,i,e,f,g,n,m,k,l,fix[500005],maxx,idx,maxx1;
vector < pair <int,int> > v[500005];
vector <int> v1;
stack <int> ms;
void dfs(int x,int y,int z) {
fix[x]=1;
if(maxx<z) { maxx=z; idx=x; }
for(int i=0;i<v[x].size();i++) {
if(v[x][i].first==y) continue;
dfs(v[x][i].first,x,z+v[x][i].second);
}
}
void dfs1(int x,int y,int z,int p) {
if(z!=-1 && k==0) ms.push(v[z][p].second);
for(int i=0;i<v[x].size();i++) {
if(v[x][i].first==z) continue;
dfs1(v[x][i].first,y,x,i);
}
if(x==y) k=1;
if(k==0) ms.pop();
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++) {
v[A[i]].push_back( { B[i] , T[i] } );
v[B[i]].push_back( { A[i] , T[i] } );
}
for(int i=0;i<N;i++) {
if(fix[i]) continue;
//cout<<i<<" ";
maxx=0; idx=-1;
dfs(i,-1,0);
a=idx;
maxx=0; idx=-1;
dfs(a,-1,0);
b=idx;
maxx1=max(maxx1,maxx); k=0;
dfs1(a,b,-1,0);
//cout<<a<<" "<<b<<" "<<maxx<<" ";
if(ms.empty()) v1.push_back(0);
a=0;
while(!ms.empty()) {
//cout<<ms.top()<<"-";
a+=ms.top();
if(a==maxx/2 && maxx%2==0) { v1.push_back(maxx/2); break; }
else if(a>maxx/2) {
v1.push_back(min(a,max(a-ms.top(),maxx-a+ms.top())));
break;
}
ms.pop();
}
while(!ms.empty()) ms.pop();
//cout<<v1[v1.size()-1]<<endl;
}
sort(v1.begin(),v1.end());
if(v1.size()>=2) maxx1=max(maxx1,v1[v1.size()-1]+v1[v1.size()-2]+L);
if(v1.size()>=3) maxx1=max(maxx1,v1[v1.size()-2]+v1[v1.size()-3]+2*L);
return maxx1;
}/*
int main() {
int a1[]={};
int b1[]={};
int c1[]={};
cout<<travelTime(2, 0, 2, a1, b1, c1);
}*/
