#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxn = 1e5;
bool vis[maxn];
vector<pair<int, int>> adj[maxn];
int comp[maxn];
int cnt;
struct NODE{
int max1, max2, id1, id2;
inline NODE(){
max1 = max2 = id1 = id2 = -1;
}
} node[maxn];
void DFS(int u, int p){
vis[u] = true;
node[u].max1 = 0; node[u].id1 = u;
for (auto [v, w] : adj[u]) if (v != p){
DFS(v, u);
if (node[v].max1 + w >= node[u].max1){
node[u].max2 = node[u].max1;
node[u].id2 = node[u].id1;
node[u].max1 = node[v].max1 + w;
node[u].id1 = v;
}
else if (node[v].max1 + w > node[u].max2){
node[u].max2 = node[v].max1 + w;
node[u].id2 = v;
}
}
// cout << u << ' ' << node[u].max1 << ' ' << node[u].max2 << '\n';
return;
}
int solve(int u, int p, int pre_len){
int res = max(pre_len, node[u].max1);
for (auto [v, w] : adj[u]) if (v != p){
int down = pre_len + w;
if (v != node[u].id1){
down = max(down, node[u].max1 + w);
res = min(res, solve(v, u, down));
}
else{
down = max(down, node[u].max2 + w);
res = min(res, solve(v, u, down));
}
}
return res;
}
pair<int, int> parameter(int u, int p){
pair<int, int> res = {0, u};
for (auto [v, w] : adj[u]) if (v != p){
pair<int, int> d = parameter(v, u);
if (d.first + w > res.first)
res.first = d.first + w, res.second = d.second;
}
return res;
}
int travelTime(int n, int m, int L, int a[], int b[], int t[]){
int ans = 0;
memset(vis, false, sizeof(vis));
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]});
}
for (int i = 0; i < n; ++i) if (!vis[i]){
DFS(i, -1);
comp[cnt] = solve(i, -1, 0);
pair<int, int> d = parameter(i, -1);
d = parameter(d.second, -1);
ans = max(ans, d.first);
cnt++;
}
sort(comp, comp + cnt);
int cur = comp[cnt - 1];
for (int i = 0; i < cnt - 1; ++i){
ans = max(ans, L + cur + comp[i]);
cur = max(max(cur, comp[i]), min(cur, comp[i]) + L);
}
return ans;
}
