#include "dreaming.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
vector <pair<int, int>> g[MAX+2];
vector <int> st(MAX+2, 0), col(MAX+2, 0);
int w;
void dfs(int u, int c=-1) {
col[u] = 1;
st[u] = 0;
for (auto &i : g[u]) {
if (i.ff == c) continue;
dfs(i.ff, u);
st[u] += i.ss + st[i.ff];
w += i.ss;
}
}
int get(int u, int c=-1) {
for (auto &i : g[u]) {
if (i.ff == c) continue;
if ((st[i.ff] + i.ss) * 2 > w) return get(i.ff, u);
}
return u;
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for (int i = 0; i < m; i++) {
g[A[i] + 1].pb({B[i]+1, T[i]});
g[B[i] + 1].pb({A[i]+1, T[i]});
}
vector <int> a;
for (int i = 1; i <= n; i++) {
if (col[i]) continue;
w = 0;
dfs(i);
int c = get(i);
dfs(c);
int mx = 0;
for (auto &j : g[i]) {
mx = max(mx, st[j.ff] + j.ss);
}
a.pb(mx);
}
sort(all(a),greater<int>());
if (a.size() == 1) return a[0];
if (a.size() == 2) return a[0] + a[1] + L;
return max(a[0] + a[1] + L, a[0] + a[2] + 2 * L);
}
