#include "dreaming.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
//typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> myset;
const ll DIM = 100007, INF = 2000000000000000007, MOD = 998244353, split = 1000;
ll t, n, m, z, q, nn,mm,kk, par[DIM], di[DIM], cl, cr, f, prev, mid, p, res2, nComp = 0, ans1, ans2, res, mi, pos, pos1, pos2, sum, ct, y, k, tt, x, t1, t2, mi1 = INF, ma1 = -INF, mi2 = INF, ma2 = -INF, v, l = INF, r = -INF, u, w, ma = -INF, id, lx, xd, yd;
bool flag;
pll comp[DIM];
vector<pll> g[DIM];
vector<ll> usedVertex;
bool used[DIM];
void dfs(ll v, ll p = -1, ll dp = 0, ll d = 0) {
usedVertex.push_back(v);
if(d > ma) {ma = max(ma, d); u = v;}
used[v] = 1;
di[v] = dp;
par[v] = p;
for(auto [u, w] : g[v])
if(!used[u]) {dfs(u, v, w, d + w); z+=w;}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<m;++i) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
l = 0;
for(int i =0;i<n;++i){
if(!used[i]) {
l++;
usedVertex.clear();
u = i, ma = 0, z = 0;
dfs(i);
for(auto u : usedVertex) used[u] = 0;
ma = 0;
dfs(u);
k = 0; res = abs(ma - k); f = u;
while(par[u] != -1) {
k += di[u];
ma -= di[u];
u = par[u];
if(abs(k - ma) < res) {f = u; res = abs(k - ma);}
}
comp[l] = {f, z};
}
}
f = comp[1].fr, z = comp[1].sc;
for(int i=2;i<=l;++i){
g[f].push_back({comp[i].fr, L});
g[comp[i].fr].push_back({f, L});
if(z < comp[i].sc) {f = comp[i].fr;}
z += comp[i].sc + L;
}
for(int i = 0;i<n;++i) used[i] = 0;
u = 0; ma = 0;
dfs(u);
for(int i=0;i<n;++i)used[i]=0;
ma = 0, dfs(u);
return ma;
}
