#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr int inf = 1e9;
vector<bool> vis;
vector<vector<pair<int, int>>> g;
vector<int> dp1, dp2, res, nodes;
void dfs_down(int u, int p) {
nodes.push_back(u);
vis[u] = 1;
for (auto [v, w] : g[u]) {
if (v == p) continue;
dfs_down(v, u);
if (dp1[v] + w > dp1[u]) {
dp2[u] = dp1[u];
dp1[u] = dp1[v] + w;
} else {
dp2[u] = max(dp2[u], dp1[v] + w);
}
}
res[u] = max(res[u], dp1[u]);
}
void dfs(int u, int p, int up) {
res[u] = max(res[u], up);
for (auto [v, w] : g[u]) {
if (v == p) continue;
int mx = 0;
if (dp1[v] + w == dp1[u]) {
mx = dp2[u];
} else {
mx = dp1[u];
}
dfs(v, u, max(up, mx) + w);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
g.resize(n);
vis.resize(n);
dp1.resize(n);
dp2.resize(n);
res.resize(n);
for (int i = 0; i < m; i++) {
int u = a[i], v = b[i], w = t[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
int ans = 0;
vector<int> x;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs_down(i, -1);
dfs(i, -1, 0);
int mn = inf;
for (auto j : nodes) {
ans = max(ans, res[j]);
mn = min(mn, res[j]);
}
x.push_back(mn);
for (auto j : nodes) {
dp1[j] = dp2[j] = res[j] = 0;
}
nodes.clear();
}
}
sort(x.rbegin(), x.rend());
if (x.size() >= 2) {
ans = max(ans, x[0] + x[1] + l);
}
if (x.size() >= 3) {
ans = max(ans, x[1] + x[2] + 2 * l);
}
return ans;
}
