#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 1e5;
vector<vector<pair<int, int>>> adj(MAXN);
vector<bool> vis(MAXN, false);
vector<int> dist(MAXN, 0);
int curmn = -1, curmx = -1; // {radius, diameter}
void dfs(int u, int par)
{
vis[u] = true;
dist[u] = 0;
for (auto [v, d] : adj[u])
{
if (v == par)
continue;
if (!vis[v])
{
dfs(v, u);
dist[u] = max(dist[u], dist[v] + d);
}
}
}
void reroot(int u, int par)
{
int mx1 = 0, mx2 = 0;
for (auto &[v, d] : adj[u])
{
if (v == par)
continue;
int val = dist[v] + d;
if (val > mx1)
{
mx2 = mx1;
mx1 = val;
}
else if (val > mx2)
mx2 = val;
}
int old = dist[u];
dist[u] = mx1;
curmn = min(curmn, dist[u]);
curmx = max(curmx, mx1 + mx2);
for (auto &[v, d] : adj[u])
{
if (v == par)
continue;
int saved = dist[u];
if (dist[v] + d == mx1)
dist[u] = mx2;
reroot(v, u);
dist[u] = saved;
}
dist[u] = old;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i = 0; i < M; ++i)
{
int u = A[i], v = B[i], d = T[i];
adj[u].push_back({v, d});
adj[v].push_back({u, d});
}
vector<int> a;
int globalDia = 0;
for (int i = 0; i < N; ++i)
{
if (vis[i])
continue;
dfs(i, -1);
curmn = INF;
curmx = 0;
reroot(i, -1);
a.push_back(curmn);
globalDia = max(globalDia, curmx);
}
sort(a.rbegin(), a.rend());
int ans = 0;
if (a.size() >= 2)
ans = max(ans, a[0] + L + a[1]);
if (a.size() >= 3)
ans = max(ans, a[1] + 2 * L + a[2]);
return max(ans, globalDia);
}
