#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxN = 100005;
vector <pair <int, int>> G[maxN];
int dpUp[maxN], dp[maxN], diam[maxN];
pair <int, int> dpDown[maxN], dpDown2[maxN];
bool seen[maxN];
void dfsDown(int nod, int tata) {
for (auto [fiu, cost] : G[nod]) {
if (fiu == tata) {
continue;
}
dfsDown(fiu, nod);
pair <int, int> p = {dpDown[fiu].first + cost, fiu};
if (p > dpDown[nod]) {
dpDown2[nod] = dpDown[nod];
dpDown[nod] = p;
} else if (p > dpDown2[nod]) {
dpDown2[nod] = p;
}
}
}
void dfsUp(int nod, int tata, int cost) {
if (tata != -1) {
dpUp[nod] = dpUp[tata] + cost;
if (dpDown[tata].second == nod) {
dpUp[nod] = max(dpUp[nod], dpDown2[tata].first + cost);
} else {
dpUp[nod] = max(dpUp[nod], dpDown[tata].first + cost);
}
}
for (auto [fiu, cost] : G[nod]) {
if (fiu == tata) {
continue;
}
dfsUp(fiu, nod, cost);
}
}
int dfs(int nod, int tata) {
seen[nod] = 1;
int ans = max(dpDown[nod].first, dpUp[nod]);
for (auto [fiu, _] : G[nod]) {
if (fiu == tata) {
continue;
}
ans = min(ans, dfs(fiu, nod));
}
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]].push_back({B[i], T[i]});
G[B[i]].push_back({A[i], T[i]});
}
int cnt = 0;
for (int i = 0; i < N; i++) {
if (seen[i]) {
continue;
}
dfsDown(i, -1);
dfsUp(i, -1, 0);
diam[cnt] = dfs(i, -1);
cnt++;
}
sort(diam, diam + cnt);
reverse(diam, diam + cnt);
if (cnt == 1) {
return diam[0];
}
if (cnt == 2) {
return diam[0] + diam[1] + L;
}
return max(diam[0] + diam[1] + L, diam[1] + diam[2] + 2 * L);
}
