#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int, int>>> vvi(N);
for (int i = 0; i < M; i++)
vvi[A[i]].push_back({ B[i], T[i] }), vvi[B[i]].push_back({ A[i], T[i] });
vector<int> dp(N);
vector<bool> visi(N);
function<int(int)> fii = [&](int cur) -> int {
if (visi[cur]) return -1e9;
visi[cur] = 1;
for (auto& a : vvi[cur]) {
dp[cur] = max(dp[cur], fii(a.first) + a.second);
}
return dp[cur];
};
for (int i = 0; i < N; i++) {
fii(i);
}
vector<int> dp2(N);
visi.assign(N, 0);
function<void(int, int)> fii2 = [&](int cur, int up) {
if (visi[cur]) return;
visi[cur] = 1;
dp2[cur] = up;
multiset<int> si = { up };
for (auto a : vvi[cur]) {
if (visi[a.first] == 1) continue;
si.insert(a.second + dp[a.first]);
}
for (auto a : vvi[cur]) {
if (visi[a.first] == 1) continue;
si.erase(si.find(a.second + dp[a.first]));
fii2(a.first, a.second + *si.rbegin());
si.insert(a.second + dp[a.first]);
}
};
for (int i = 0; i < N; i++) {
fii2(i, 0);
}
vector<int> compo(N, -1);
function<void(int, int)> fii3 = [&](int cur, int comp) {
if (compo[cur] != -1) return;
compo[cur] = comp;
for (auto a : vvi[cur]) fii3(a.first, comp);
};
int cur = 0;
for (int i = 0; i < N; i++) {
if (compo[i] == -1) fii3(i, cur++);
}
vector<int> all(cur, 1e9);
for (int i = 0; i < N; i++) {
all[compo[i]] = min(all[compo[i]], max(dp[i], dp2[i]));
}
sort(all.rbegin(), all.rend());
if (cur == 1) {
return all[0];
}
else if (cur == 2) {
return all[0] + all[1] + L;
}
else {
return max(all[0] + all[1] + L, all[1] + all[2] + 2 * L);
}
}
