#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=1e5+50;
vector<pair<int,int>>E[N];
int n,m;
bool was[N];
ll dist[N];int par[N];
vector<int>vtx;
void DFS(int u,int p=-1){
vtx.pb(u);
par[u]=p;
if(p==-1)dist[u]=0;
for(auto [v,w]:E[u])if(v!=p){
dist[v]=dist[u]+w;
DFS(v,u);
}
}
int travelTime(int n1, int m1, int L, int A[], int B[], int T[]){
n=n1,m=m1;
for(int i=0;i<m;i++){
E[A[i]].pb({B[i],T[i]});
E[B[i]].pb({A[i],T[i]});
}
vector<pair<int,ll>>vts;
for(int i=0;i<n;i++)if(!was[i]){
vtx.clear();
DFS(i);
for(auto j:vtx)was[j]=true;
ll mx=0;
for(auto j:vtx)mx=max(mx,dist[j]);
int U=-1;
for(auto j:vtx)if(mx==dist[j])U=j;
vtx.clear();
DFS(U);
mx=0;
for(auto j:vtx)mx=max(mx,dist[j]);
int V=-1;
for(auto j:vtx)if(mx==dist[j])V=j;
ll mn=1e18;int x=U;
for(int v=V;v!=U;v=par[v]){
if(max(dist[v],dist[V]-dist[v])<mn)mn=max(dist[v],dist[V]-dist[v]),x=v;
}
vts.pb({x,max(dist[x],dist[V]-dist[x])});
}
sort(vts.begin(),vts.end(),[&](pair<int,ll>x,pair<int,ll>y){return x.se>y.se;});
for(int i=1;i<(int)vts.size();i++){
E[vts[0].fi].pb({vts[i].fi,L});
E[vts[i].fi].pb({vts[0].fi,L});
}
DFS(1);
ll res=0;
for(int i=0;i<n;i++)res=max(res,dist[i]);
int U=-1;
for(int i=0;i<n;i++)if(dist[i]==res)U=i;
DFS(U);
res=0;
for(int i=0;i<n;i++)res=max(res,dist[i]);
return res;
}
