#include <bits/stdc++.h>
#include "dreaming.h"
#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;
template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
return a < b ? (a = b, true) : false;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 10;
vector <pair <int, int>> adj[maxN];
int flag[maxN], dp_up[maxN], dp_down[maxN], diameter[maxN], d[maxN];
vector <int> root;
int cur_res = 0;
void dfs(int u)
{
flag[u] = 1;
for (auto &e: adj[u])
{
int v = e.fi, w = e.se;
if (!flag[v])
{
dfs(v);
uax(dp_down[u], dp_down[v] + w);
}
}
}
void dfs2(int u, int S)
{
flag[u] = 1;
uax(diameter[S], dp_up[u] + dp_down[u]);
uin(d[S], max(dp_up[u], dp_down[u]));
vector <pair <int, int>> edges;
for (auto &e: adj[u])
{
if (!flag[e.fi])
{
edges.eb(e);
}
}
if (edges.empty())
{
//u is leaf
return;
}
//prefixes
int mx = dp_down[edges[0].fi] + edges[0].se;
for (int i = 1; i < (int)edges.size(); i++)
{
dp_up[edges[i].fi] = mx + edges[i].se;
uax(mx, dp_down[edges[i].fi] + edges[i].se);
}
//suffixes
mx = dp_down[edges.back().fi] + edges.back().se;
for (int i = (int)edges.size() - 2; i >= 0; i--)
{
uax(dp_up[edges[i].fi], mx + edges[i].se);
uax(mx, dp_down[edges[i].fi] + edges[i].se);
}
for0(i, edges.size())
{
uax(dp_up[edges[i].fi], dp_up[u] + edges[i].se);
}
mx = 0;
for (auto &e: adj[u])
{
if (!flag[e.fi])
{
dfs2(e.fi, S);
uax(diameter[S], mx + e.se + dp_down[e.fi]);
uax(mx, e.se + dp_down[e.fi]);
}
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
for0(i, m)
{
int u = A[i] + 1, v = B[i] + 1, w = T[i];
adj[u].eb(v, w);
adj[v].eb(u, w);
}
for1(i, n)
{
if (!flag[i])
{
root.eb(i);
dfs(i);
}
}
fill(flag + 1, flag + n + 1, 0);
fill(d + 1, d + n + 1, 1e9);
for1(i, n)
{
if (!flag[i])
{
dfs2(i, i);
}
}
int ans = 1e9;
if ((int)root.size() > 1)
{
sort(all(root), [](int x, int y)
{
return d[x] < d[y];
});
for (int i = 0; i < (int)root.size(); i++)
{
int r = root[i], cur = 0;
//r is root
if (i == (int)root.size() - 1)
{
uax(cur, d[r] + d[root[i - 1]] + L);
}
else
{
uax(cur, d[r] + d[root.back()] + L);
}
if ((int)root.size() >= 3)
{
int u, v, cnt = 0;
for (int j = (int)root.size() - 1; j >= 0; j--)
{
if (j == i)
{
continue;
}
if (cnt == 0)
{
u = root[j];
}
else if (cnt == 1)
{
v = root[j];
}
else
{
break;
}
cnt++;
}
uax(cur, d[u] + d[v] + L * 2);
}
uin(ans, cur);
}
}
else
{
ans = 0;
}
for (auto &r: root)
{
uax(ans, diameter[r]);
}
return ans;
}
