#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr int N = 100000;
vector<pair<int, int>> adj[N];
int dp[N], now = numeric_limits<int>::max(), ans = 0;
bool used[N];
void dfs1(int v, int par) {
used[v] = true;
for (auto [to, w] : adj[v]) {
if (to != par) {
dfs1(to, v);
ans = max(ans, dp[v] + dp[to] + w);
dp[v] = max(dp[v], dp[to] + w);
}
}
}
void dfs2(int v, int par, int up) {
now = min({now, max(up, dp[v])});
vector<int> pref(adj[v].size() + 1);
for (int i = 0; i < adj[v].size(); ++i) {
pref[i + 1] = pref[i];
auto [to, w] = adj[v][i];
if (to == par) {
continue;
}
pref[i + 1] = max(pref[i + 1], dp[to] + w);
}
for (int i = int(adj[v].size()) - 1; i >= 0; --i) {
auto [to, w] = adj[v][i];
if (to == par) {
continue;
}
dfs2(to, v, max(pref[i], up) + w);
up = max(up, dp[to] + w);
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for (int i = 0; i < m; ++i) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
vector<int> arr;
for (int i = 0; i < n; ++i) {
if (!used[i]) {
now = numeric_limits<int>::max();
dfs1(i, -1);
dfs2(i, -1, 0);
arr.push_back(now);
}
}
sort(arr.rbegin(), arr.rend());
if (arr.size() > 1) {
ans = max(ans, arr[0] + arr[1] + L);
}
if (arr.size() > 2) {
ans = max(ans, arr[1] + arr[2] + 2 * L);
}
return ans;
}
