#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
int dfs(int u,const vector<vector<pair<int,int> > >& g,int p=-1)
{
int mx=0;
for(auto [v,w]:g[u])
{
if(v==p) continue;
mx=max(mx,w+dfs(v,g,u));
}
return mx;
}
int getrep(int u,const vector<vector<pair<int,int> > >& g,vector<bool>& vis,const vector<int>& D)
{
vis[u]=true;
int mn=D[u];
for(auto [v,w]:g[u])
{
if(vis[v]) continue;
mn=min(mn,getrep(v,g,vis,D));
}
return mn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int,int> > > g(N);
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]});
}
vector<int> D(N);
vector<int> reps;
for(int i=0;i<N;i++)
{
D[i]=dfs(i,g);
}
vector<bool> vis(N,false);
for(int i=0;i<N;i++)
{
if(vis[i]) continue;
reps.push_back(getrep(i,g,vis,D));
}
sort(reps.rbegin(),reps.rend());
int ans=reps[0];
if(reps.size()>1) ans=max(ans,L+reps[0]+reps[1]);
if(reps.size()>2) ans=max(ans,2*L+reps[1]+reps[2]);
return ans;
}
