#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], dist2[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);
}
}
}
ll mn, f;
void get(ll x,ll p){
ll val = max(dist[x], dist2[x]);
if(val < mn){
mn = val;
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(int i = 0; i < n; i++){
adj[i].clear();
vis[i] = 0;
}
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;
for(ll i = 0; i < n; i++){
if(!vis[i]){
ll g=i;
mx = 0;
dfs(i,-1,0,g);
ll A = g;
mx = 0;
dfs(A,-1,0,g);
ll B = g;
mix = max(mix, mx);
dps(A,-1,0,dist);
dps(B,-1,0,dist2);
mn = 1e18;
get(A,-1);
center.pb(mn);
mark(i);
}
}
sort(center.rbegin(), center.rend());
if(center.size() == 1) ertunt mix;
if(center.size() == 2){
ertunt max(mix, center[0] + center[1] + l);
}
ertunt max({mix, center[0] + center[1] + l, center[1] + center[2] + 2*l});
}
