#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr int N = 1e5;
struct Graph {
vector<vector<pair<int, int>>> g;
vector<int> dp1, dp2, res;
int x, cnt;
vector<int> node;
Graph() {
g.resize(N);
dp1.resize(N);
dp2.resize(N);
res.resize(N);
x = cnt = 0;
}
void add(int a, int b, int w) {
if (g[a].empty()) node.push_back(a);
if (g[b].empty()) node.push_back(b);
x = a;
g[a].push_back({b, w});
g[b].push_back({a, w});
cnt++;
}
void dfs1(int u, int p) {
for (auto [v, w] : g[u]) {
if (v == p) continue;
dfs1(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 dfs2(int u, int p, int d) {
res[u] = max(res[u], d);
for (auto [v, w] : g[u]) {
if (v == p) continue;
int k = 0;
if (dp1[v] + w == dp1[u]) {
k = dp2[u];
}
else {
k = dp1[u];
}
dfs2(v, u, max(k, d) + w);
}
}
void process() {
dfs1(x, -1);
dfs2(x, -1, 0);
}
array<int, 2> findmin() {
process();
int mn = 1e9;
for (auto u : node) {
mn = min(mn, res[u]);
}
for (auto u : node) {
if (res[u] == mn) {
return {mn, u};
}
}
return {};
}
bool empty() {
return cnt == 0;
}
void clear() {
for (auto u : node) {
g[u].clear();
dp1[u] = dp2[u] = res[u] = 0;
}
node.clear();
x = cnt = 0;
}
};
vector<pair<int, int>> adj[N];
vector<Graph> g;
Graph tmp;
bool vis[N];
void dfs(int u) {
vis[u] = 1;
for (auto [v, w] : adj[u]) {
if (!vis[v]) {
tmp.add(u, v, w);
dfs(v);
}
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
Graph res;
vector<bool> is(n);
for (int i = 0; i < m; i++) {
int u = a[i], v = b[i], w = t[i];
is[u] = is[v] = 1;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
res.add(u, v, w);
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
tmp.clear();
dfs(i);
g.push_back(tmp);
}
}
set<array<int, 2>> v;
for (int i = 0; i < n; i++) {
if (!is[i]) {
v.insert({0, i});
}
}
for (int i = 0; i < g.size(); i++) {
if (!g[i].empty()) {
v.insert(g[i].findmin());
}
}
vector<int> k;
for (auto p : v) {
k.push_back(p[1]);
}
ranges::reverse(k);
for (int i = 1; i < v.size(); i++) {
res.add(k[i], k[i - 1], l);
}
res.findmin();
int ans = 0;
for (int i = 0; i < N; i++) {
ans = max(ans, res.res[i]);
}
return ans;
}
