#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
vector<pair<int, int>> g[maxn];
pair<int, int> len[maxn];
vector<int> arr;
bool vis[maxn];
void add(int x, int t) {
if (t >= len[x].first) {
len[x].second = len[x].first;
len[x].first = t;
} else {
len[x].second = max(len[x].second, t);
}
}
int dfs(int x, int p) {
vis[x] = 1;
len[x] = {0, 0};
for (auto e : g[x]) {
if (e.first == p) continue;
dfs(e.first, x);
add(x, len[e.first].first+e.second);
}
}
int dfs_reroot(int x, int p, int r) {
if (~p) {
if (len[p].first == len[x].first+r) {
add(x, len[p].second+r);
} else {
add(x, len[p].first+r);
}
}
int ans = x;
for (auto e : g[x]) {
if (e.first == p) continue;
int v = dfs_reroot(e.first, x, e.second);
if (len[ans].first > len[v].first) {
ans = v;
}
}
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i=0; i<N; ++i) g[i].clear(), vis[i] = 0;
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]);
}
for (int i=0; i<N; ++i) {
if (vis[i]) continue;
dfs(i, -1);
arr.emplace_back(dfs_reroot(i, -1, 0));
}
sort(arr.begin(), arr.end(), [&](int x, int y) {
return len[x].first > len[y].second;
});
for (int i = 1; i < arr.size(); ++i) {
g[arr[0]].emplace_back(arr[i], L);
g[arr[i]].emplace_back(arr[0], L);
}
dfs(0, -1);
dfs_reroot(0, -1, 0);
int ans = 0;
for (int i = 0; i < N; ++i) {
ans = max(ans, len[i].first);
}
return ans;
}
