#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "dreaming.h"
using namespace std;
const int inf = 7 + 1e9;
vector <int> vis, f, g;
vector <vector <II>> adj;
int dfs(int u) {
int ans = 0, ma1 = 0, ma2 = -1;
vis[u] = 1;
for (auto z : adj[u]) {
int v = z.st, w = z.nd;
if (vis[v])
continue;
ans = max(ans, dfs(v));
f[u] = max(f[u], f[v] + w);
if (f[v] + w > ma1) {
ma2 = ma1;
ma1 = f[v] + w;
}
else if (f[v] + w > ma2)
ma2 = f[v] + w;
}
if (ma2 >= 0)
ma1 += ma2;
return max(ans, ma1);
}
int dfs_(int u, int p) {
int ans = max(f[u], g[u]);
vector <II> V;
for (auto z : adj[u])
if (z.st != p)
V.push_back(z);
vector <int> l(V.size(), 0), r(V.size(), 0);
for (int i = 1; i < V.size(); i ++)
l[i] = max(l[i - 1], f[V[i - 1].st] + V[i - 1].nd);
for (int i = (int)V.size() - 2; i >= 0; i --)
r[i] = max(r[i + 1], f[V[i + 1].st] + V[i + 1].nd);
for (int i = 0; i < V.size(); i ++) {
int v = V[i].st, w = V[i].nd;
g[v] = max({l[i], r[i], g[u]}) + w;
ans = min(ans, dfs_(v, u));
}
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
for (int i = 0; i < M; i ++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
vis.assign(N, 0);
f.assign(N, 0);
g.assign(N, 0);
vector <int> c;
int ma = 0;
for (int i = 0; i < N; i ++)
if (!vis[i]) {
ma = max(ma, dfs(i));
int val = dfs_(i, 0);
c.push_back(val);
}
if (c.size() == 1)
return max(ma, c[0]);
if (c.size() == 2)
return max(ma, c[0] + c[1] + L);
vector <vector <int>> l(c.size(), vector <int> (2, 0)), r(c.size(), vector <int> (2, 0));
for (int i = 1; i < c.size(); i ++) {
l[i][0] = l[i - 1][0];
l[i][1] = l[i - 1][1];
if (c[i - 1] > l[i][0]) {
l[i][1] = l[i][0];
l[i][0] = c[i - 1];
}
else if (c[i - 1] > l[i][1])
l[i][1] = c[i - 1];
}
for (int i = (int)c.size() - 2; i >= 0; i --) {
r[i][0] = r[i + 1][0];
r[i][1] = r[i + 1][1];
if (c[i + 1] > r[i][0]) {
r[i][1] = r[i][0];
r[i][0] = c[i + 1];
}
else if (c[i + 1] > r[i][1])
r[i][1] = c[i + 1];
}
int ans = inf;
for (int i = 0; i < c.size(); i ++) {
int ma1 = l[i][0], ma2 = l[i][1];
for (int j = 0; j < 2; j ++)
if (r[i][j] > ma1) {
ma2 = ma1;
ma1 = r[i][j];
}
else if (r[i][j] > ma2)
ma2 = r[i][j];
ans = min(ans, max(ma1 + c[i] + L, ma1 + ma2 + 2 * L));
}
return max(ans, ma);
}
