#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int N = 1e5 + 5;
struct node {
int mx, lazy;
node() {
mx = 0;
lazy = 0;
}
node operator + (const node& o) const {
node res;
res.mx = max(mx, o.mx);
return res;
}
};
node it[N << 2];
void upd(int k, int val) {
it[k].lazy += val;
it[k].mx += val;
}
void shift(int k) {
upd(k << 1, it[k].lazy);
upd(k << 1 | 1, it[k].lazy);
it[k].lazy = 0;
}
void update(int k, int l, int r, int u, int v, int val) {
if(l > v || r < u) return;
if(u <= l && r <= v) {
upd(k, val);
return;
}
shift(k);
int mid = l + r >> 1;
update(k << 1, l, mid, u, v, val);
update(k << 1 | 1, mid + 1, r, u, v, val);
it[k] = it[k << 1] + it[k << 1 | 1];
}
int n, m, L;
vector<pair<int, int>> g[N];
int comps, id[N];
vector<int> ve;
vector<int> lens;
int in[N], out[N], tim;
int dist[N];
int cnt;
int dia;
void dfs(int u) {
id[u] = comps;
ve.emplace_back(u);
for(auto [v, w] : g[u]) if(id[v] != comps) {
dfs(v);
}
}
void cal(int u, int p) {
in[u] = ++tim;
for(auto [v, w] : g[u]) if(v != p) {
dist[v] = dist[u] + w;
cal(v, u);
}
out[u] = tim;
}
int best;
void reroot(int u, int p) {
best = min(best, it[1].mx);
dia = max(dia, it[1].mx);
for(auto [v, w] : g[u]) if(v != p) {
update(1, 1, cnt, 1, cnt, w);
update(1, 1, cnt, in[v], out[v], -2 * w);
reroot(v, u);
update(1, 1, cnt, 1, cnt, -w);
update(1, 1, cnt, in[v], out[v], 2 * w);
}
}
int travelTime(int _n, int _m, int _L, int A[], int B[], int T[]) {
n = _n;
m = _m;
L = _L;
for(int i = 0; i < m; ++i) {
g[A[i] + 1].emplace_back(B[i] + 1, T[i]);
g[B[i] + 1].emplace_back(A[i] + 1, T[i]);
}
for(int i = 1; i <= n; ++i) if(!id[i]) {
++comps;
ve.clear();
dfs(i);
cnt = ve.size();
dist[ve[0]] = 0;
tim = 0;
cal(ve[0], 0);
for(int j = 0; j <= cnt * 4 + 5; ++j) it[j] = node();
for(int x : ve) update(1, 1, cnt, in[x], in[x], dist[x]);
best = 2e9;
reroot(ve[0], 0);
lens.emplace_back(best);
}
sort(lens.rbegin(), lens.rend());
if((int)lens.size() == 1) return dia;
if(lens.size() == 2) return max(dia, lens[0] + lens[1] + L);
return max(dia, max(lens[0] + lens[1] + L, lens[1] + lens[2] + 2 * L));
}
