#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];
ll dist[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){
dist[x] = cur;
for(auto [y,w] : adj[x]){
if(y != p){
dps(y,x,cur+w);
}
}
}
ll mn, f;
void get(ll x,ll p){
if(dist[x] < mn){
mn = dist[x];
f = x;
}
for(auto [y,w] : adj[x]){
if(y != p)get(y,x);
}
}
bool vis[200005];
void mark(ll x){
vis[x]=1;
for(auto [y,_]:adj[x]){
if(!vis[y]) mark(y);
}
}
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);
mx = 0;
dfs(g,-1,0,g);
dps(g,-1,0);
mn = 1e18;
get(g,-1);
center.pb(f);
if(mx > mix){
mix = mx;
ce = f;
}
mark(i);
}
}
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 = 0;
mx=0;
dfs(ce,-1,0,g);
mx=0;
dfs(g,-1,0,g);
ertunt mx;
}
