#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
array<int, 2> dmax;
vector<int> id, d;
vector<vector<int>> cc;
vector<vector<pair<int, int>>> g;
void comps(int v) {
if (id[v] != -1) return;
id[v] = cc.size() - 1;
cc.back().push_back(v);
for (auto [u, w] : g[v])
comps(u);
}
void dfs(int v, int p) {
if (d[v] > dmax[1]) dmax = {v, d[v]};
for (auto [u, w] : g[v]) {
if (u == p) continue;
d[u] = d[v] + w;
dfs(u, v);
}
}
int diam(int v) {
dmax = {v, 0}; dfs(v, -1);
v = dmax[0]; d[v] = 0;
dmax = {v, 0}; dfs(v, -1);
return dmax[1];
}
bool rebuild(int v, int p, int target, vector<int>& archi) {
if (v == target) return true;
for (auto [u, w] : g[v]) {
if (u == p) continue;
if (rebuild(u, v, target, archi)) {
archi.push_back(w);
return true;
}
}
return false;
}
int coda(int v) {
dmax = {v, 0}; dfs(v, -1);
int a = dmax[0]; d[a] = 0;
dmax = {a, 0}; dfs(a, -1);
int b = dmax[0];
vector<int> archi; // archi del diametro
assert(rebuild(a, -1, b, archi));
int sum = 0;
for (int w : archi) sum += w;
int ans = sum;
for (int i = 0, p = 0; i < int(archi.size()); ++i) {
p += archi[i];
ans = min(ans, max(sum - p, p));
}
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
g.resize(N);
d.resize(N);
id.resize(N, -1);
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]});
}
for (int i = 0; i < N; ++i) {
if (id[i] == -1) {
cc.push_back(vector<int>(0));
comps(i);
}
}
int ans = 0;
for (int i = 0; i < int(cc.size()); ++i)
ans = max(ans, diam(cc[i][0]));
array<int, 3> o{};
for (int i = 0; i < int(cc.size()); ++i) {
o[2] = max(o[2], coda(cc[i][0]));
if (o[1] < o[2]) swap(o[1], o[2]);
if (o[0] < o[1]) swap(o[0], o[1]);
}
if (int(cc.size()) == 1) return ans;
ans = max(ans, o[0] + o[1] + L);
if (int(cc.size()) == 2) return ans;
ans = max(ans, o[1] + o[2] + 2*L);
return ans;
}
