#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
const int N = 1e5 + 3;
const int inf = 1e9;
int dp[N], dist[N];
bool vis[N];
multiset<int> val[N];
vector<pair<int, int>> adj[N];
int node = -1, ansnode = inf;
void dfs(int u, int p) {
vis[u] = true;
for (auto [x, w] : adj[u]) if (x != p) {
dfs(x, u);
dp[u] = max(dp[u], dp[x]+w);
val[u].insert(dp[x]+w);
}
}
void reroot(int u, int p) {
if (ansnode > dp[u]) {
node = u; ansnode = dp[u];
}
for (auto [x, w] : adj[u]) if (x != p) {
val[u].erase(val[u].find(dp[x]+w));
dp[u] = (val[u].empty() ? 0 : *val[u].rbegin());
val[x].insert(dp[u]+w);
dp[x] = *val[x].rbegin();
reroot(x, u);
val[x].erase(val[x].find(dp[u]+w));
dp[x] = (val[x].empty() ? 0 : *val[x].rbegin());
val[u].insert(dp[x]+w);
dp[u] = *val[u].rbegin();
}
}
void diam(int u, int p) {
for (auto [x, w] : adj[u]) if (x != p) {
dist[x] = dist[u]+w;
diam(x, u);
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
vector<pair<int, int>> nodes;
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]) continue;
node = -1; ansnode = inf;
dfs(i, -1);
reroot(i, -1);
nodes.push_back({dp[node], node});
dbg(node, dp[node], i);
}
sort(nodes.begin(), nodes.end(), greater<>());
for (int i = 1; i < nodes.size(); i++) {
auto [dpp, v] = nodes[i];
auto [dp1, u] = nodes[0];
adj[u].push_back({v, L});
adj[v].push_back({u, L});
}
dist[1] = 0;
diam(1, -1);
int mx = *max_element(dist, dist + n), u;
for (int i = 0; i < n; i++) if (dist[i] == mx) u = i;
dist[u] = 0;
diam(u, -1);
mx = *max_element(dist, dist + n);
return mx;
}
