#include <bits/stdc++.h>
#include "dreaming.h"
#define ii pair< int , int >
#define se second
#define fi first
using namespace std;
const int N=1e5+55;
vector < ii > vec[N];
bool visited[N];
long long d=0;
long long md=0;
long long l=1e16+5000;
long long dfs(int u , int p ,bool q)
{
// cout<<u<<' '<<p<<endl;
visited[u]=1;
long long d1=0,d2=0;
int v,c;
long long temp=0;
for(auto x:vec[u])
{
v=x.fi;
c=x.se;
if(v==p)
continue;
temp=dfs(v,u,q);
temp+=c;
if(temp>d2)
d2=temp;
if(d2>d1)
swap(d1,d2);
}
if(!q&&d<d1+d2)
d=d1+d2;
if(q)
{
if(l>max(d1,d-d1))
l=max(d1,d-d1);
}
return d1;
}
int travelTime(int n, int M, int L, int A[], int B[], int T[])
{
for(int i=0;i<M;i++)
{
vec[B[i]].push_back({A[i],T[i]});
vec[A[i]].push_back({B[i],T[i]});
}
vector < long long > ln;
memset(visited,0,sizeof visited);
for(int i=0;i<n;i++)
{
if(visited[i]==0)
{
d=0;
dfs(i,i,0);
l=1e16+5555;
dfs(i,i,1);
md=max(md,d);
if(vec[i].size()==0)
l=0;
ln.push_back(l);
}
}
sort(ln.begin(),ln.end());
int s=ln.size();
if(s==1)
return md;
if(s==2)
return max(md,ln[s-1]+ln[s-2]+L);
return max(md,max(ln[s-1]+ln[s-2]+L,ln[s-2]+ln[s-3]+L+L));
}
