#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using pii = pair<int, int>;
using pp = pair<pii, pii>;
#define F first
#define S second
const int N = 100010;
const int INF = 1e9;
inline void setmax(pp &p, pii x) {
if (x > p.F) {
p.S = p.F;
p.F = x;
} else if (x > p.S) {
p.S = x;
}
}
inline pii getmax(pp p, int x=-1) {
if (p.F.S == x) return p.S;
return p.F;
}
vector<pii> G[N];
pp dp1[N], dp2[N];
bool vis[N];
int dfs1(int u, int p) {
vis[u] = true;
pp mx(pii(0, 0), pii(0, 0));
int ans = 0;
for (auto v : G[u]) if (v.F != p) {
ans = max(ans, dfs1(v.F, u));
setmax(mx, pii(getmax(dp1[v.F]).F + v.S, v.F));
}
dp1[u] = mx;
ans = max(ans, mx.F.F + mx.S.F);
return ans;
}
pii dfs2(int u, int p, int w) {
pp mx = dp1[u];
if (p != -1)
setmax(mx, pii(getmax(dp2[p], u).F + w, p));
dp2[u] = mx;
pii ans(dp2[u].F.F, u);
for (auto v : G[u]) if (v.F != p)
ans = min(ans, dfs2(v.F, u, v.S));
return ans;
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for (int i = 0; i < m; ++i) {
G[A[i]].emplace_back(B[i], T[i]);
G[B[i]].emplace_back(A[i], T[i]);
}
vector<pii> add;
for (int u = 0; u < n; ++u) {
if (vis[u]) continue;
dfs1(u, -1);
add.push_back(dfs2(u, -1, -1));
}
sort(add.begin(), add.end(), greater<pii>());
for (int i = 1; i < add.size(); ++i) {
int u = add[0].S, v = add[i].S;
G[u].emplace_back(v, L);
G[v].emplace_back(u, L);
}
for (int u = 0; u < n; ++u) vis[u] = false;
return dfs1(0, -1);
}
