#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll array<ll, 2>
using namespace std;
const ll N = 1e5 + 5;
const ll inf = INT_MAX;
bool bl = 0;
vector<vector<pll>>g;
ll ch[N]; pll par[N];
array<int, 2> mx = {-1, -1};
void dfs(ll u, ll p = -1, ll W = 0){
ch[u] = 1;
if(W > mx[1]) mx = {(int)u, (int)W};
for(auto &[v, w]: g[u]){
if(v == p) continue;
par[v] = {u, w};
dfs(v, u, W + w);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
g.assign(n, {});
for(ll i = 0; i < m; i++){
g[a[i]].pb({b[i], t[i]});
g[b[i]].pb({a[i], t[i]});
}
vector<ll>r; int mxW = 0;
for(ll i = 0; i < n; i++){
if(ch[i]) continue;
mx = {-1, -1}; dfs(i);
ll id = mx[0]; mx = {-1, -1};
par[id] = {-1, 0}; dfs(id, 1);
ll x = mx[0], W = 0, rad = inf;
while(x >= 0){
W += par[x][1];
x = par[x][0];
rad = min(rad, max(W, mx[1] - W));
}
r.pb(rad == inf ? 0 : rad); mxW = max(mxW, mx[1]);
}
sort(r.rbegin(), r.rend());
if(r.size() < 2) return mxW;
if(r.size() == 2) return max(mxW, int(r[0] + r[1] + l));
return max({mxW, int(r[0] + r[1] + l), int(r[1] + r[2] + 2 * l)});
}
