#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll,ll>
#define pqll priority_queue<ll>
#define pqpll priority_queue<pll>
#define pqllg priority_queue<ll, vector<ll>, greater<ll>>
#define pqpllg priority_queue<pll, vector<pll>, greater<pll>>
#define inf (ll)1e17
#define vll vector<ll>
#define vqll vector<queue<ll>>
#define vpll vector<pll>
#define qll queue<ll>
#define stll stack<ll>
#define se second
#define fi first
#define umll unordered_map<ll, ll>
#define msll multiset<ll>
#define pb push_back
#define pu push
#define fr front
#define em empty
const ll maxn=1e5+2;
ll par[maxn];
ll d[maxn]; // max dist from node
ll thing[maxn]; // max dist from node in set
ll ans;
ll phase;
ll centre;
vpll adj[maxn];
ll findpar(ll a){
if(par[a]==a)return a;
return par[a]=findpar(par[a]);
}
void merge(ll a,ll b){
par[findpar(a)]=findpar(b);
}
bool visited[maxn];
pll finddiam(ll i,ll p,ll d){ // return {dist,node}
pll macks={0,i};
for(auto c:adj[i]){
if(c.se==p)continue;
pll ans=finddiam(c.se,i,d+c.fi);
macks=max(macks,{ans.fi+c.fi,ans.se});
}
if(phase>0){
if(thing[i]==inf)
thing[i]=d;
else {
if(ans>max(thing[i],d)){
ans=max(thing[i],d);
centre=i;
}
}
}
return macks;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(ll i=0;i<N;i++)par[i]=i;
for(ll i=0;i<M;i++){
merge(A[i],B[i]);
adj[A[i]].pb({T[i],B[i]});
adj[B[i]].pb({T[i],A[i]});
}
fill(visited,visited+maxn,0);
fill(thing,thing+maxn,inf);
priority_queue<pll> pq;
for(ll i=0;i<N;i++){
if(visited[findpar(i)])continue;
ans=inf;
centre=i;
phase=0;
ll aa=finddiam(i,i,0).se;
phase=1;
ll bb=finddiam(aa,aa,0).se;
phase=2;
ll cc=finddiam(bb,bb,0).se;
pq.pu({ans,centre});
visited[findpar(i)]=1;
}
ll ma=pq.top().se;pq.pop();
while(!pq.empty()){
ll i=pq.top().se;
adj[i].pb({L,ma});
adj[ma].pb({L,i});
pq.pop();
}
ll aa=finddiam(0,0,0).se;
return finddiam(aa,aa,0).fi;
}
