#include <bits/stdc++.h>
#include "dreaming.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int NN=1e5+5;
int l[NN],d[NN],p[NN];
vector <int> gr[NN];
vector <pair <int,int> >g[NN];
int find_set(int v){
if(l[v]==v)return v;
return l[v]=find_set(l[v]);
}
void union_set(int u,int v){
u=find_set(u);
v=find_set(v);
if(u!=v){
if(gr[v].size()<gr[u].size())swap(u,v);
l[u]=v;
for(auto x : gr[u])gr[v].pb(x);
gr[u].clear();
}
}
void bfs(int v){
queue <int> q;
q.push(v);
while(!q.empty()){
int v=q.front();
q.pop();
for(auto to : g[v]){
if(d[to.ff]==-1){
p[to.ff]=v;
d[to.ff]=d[v]+to.ss;
q.push(to.ff);
}
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<N;i++){
l[i]=i;
gr[i].pb(i);
}
for(int i=0;i<M;i++){
union_set(A[i],B[i]);
g[A[i]].pb({B[i],T[i]});
g[B[i]].pb({A[i],T[i]});
}
vector <int> len;
int ans=0;
for(int i=0;i<N;i++)d[i]=-1;
for(int i=0;i<N;i++){
if(gr[i].size()!=0){
d[gr[i][0]]=0;
bfs(gr[i][0]);
int mx=0,node=gr[i][0];
for(auto x : gr[i]){
if(d[x]>mx){
mx=d[x];
node=x;
}
d[x]=-1;
p[x]=0;
}
d[node]=0;
bfs(node);
mx=0;
int s=node;
for(auto x : gr[i]){
if(d[x]>mx){
mx=d[x];
node=x;
}
}
ans=max(ans,mx);
vector <int> path;
path.pb(node);
while(node!=s){
node=p[node];
path.pb(node);
}
int mn=1e9+5;
for(auto x : path){
mn=min(max(mx-d[x],d[x]),mn);
}
len.pb(mn);
for(auto x : gr[i]){
d[x]=-1;
p[x]=0;
}
}
}
sort(all(len));
for(auto x : len)ans=max(ans,x);
if(len.size()>=2)ans=max(ans,L+len[len.size()-1]+len[len.size()-2]);
if(len.size()>=3)ans=max(ans,2*L+len[len.size()-2]+len[len.size()-3]);
return ans;
}
