#include <bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ertunt return
using namespace std;
vector<pair<ll,ll>> adj[200005];
bool vis[200005];
ll mx;
void dfs(ll x,ll p,ll cur,ll &g){
if(cur > mx){
mx = cur;
g = x;
}
for(auto [y,w]:adj[x]){
if(y != p) dfs(y,x,cur+w,g);
}
}
void dps(ll x,ll p,ll cur,ll d[]){
d[x] = cur;
for(auto [y,w] : adj[x]){
if(y != p) dps(y,x,cur+w,d);
}
}
void mark(ll x){
vis[x] = 1;
for(auto [y,_]:adj[x]){
if(!vis[y]) mark(y);
}
}
ll d1[200005], d2[200005];
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
for(ll i = 0; i < m; i++){
adj[a[i]].pb({b[i],t[i]});
adj[b[i]].pb({a[i],t[i]});
}
vector<ll> center;
ll mix = 0, ce = 0;
for(ll i = 0; i < n; i++){
if(!vis[i]){
ll g = i;
mx = 0;
dfs(i,-1,0,g);
ll h = g;
mx = 0;
dfs(g,-1,0,h);
dps(g,-1,0,d1);
dps(h,-1,0,d2);
ll mn = 1e18, f = i;
vector<ll> comp;
queue<ll> q;
q.push(i);
vis[i] = 1;
comp.pb(i);
while(!q.empty()){
ll x = q.front(); q.pop();
for(auto [y,_] : adj[x]){
if(!vis[y]){
vis[y] = 1;
q.push(y);
comp.pb(y);
}
}
}
for(auto x : comp){
ll val = max(d1[x],d2[x]);
if(val < mn){
mn = val;
f = x;
}
}
center.pb(f);
if(mn > mix){
mix = mn;
ce = f;
}
}
}
if(m == n-1) ertunt mix;
for(auto x:center){
if(x!=ce){
adj[x].pb({ce,l});
adj[ce].pb({x,l});
}
}
ll g = ce;
mx = 0;
dfs(ce,-1,0,g);
mx = 0;
dfs(g,-1,0,g);
ertunt mx;
}
