#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ff first
#define ss second
#define pii pair<int, int>
int cnt;
vector<int> v, u, vis;
vector<pii> a;
vector<vector<pii>> E;
int dfsv(int x, int p = -1) {
for (auto [i, w] : E[x])
if (i != p) v[x] = max(v[x], w + dfsv(i, x));
return v[x];
}
void dfsu(int x) {
vis[x] = cnt;
for (auto [i, w] : E[x])
if (!vis[i]) a.push_back({w + v[i], i});
sort(a.rbegin(), a.rend());
for (auto [i, w] : E[x])
if (!vis[i]) u[i] = w + max(u[x], (a[0].ss != i ? a[0].ff : (1 < (int)a.size() ? a[1].ff : 0)));
a.clear();
for (auto [i, w] : E[x])
if (!vis[i]) dfsu(i);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
E.assign(n, {});
for (int i = 0; i < m; i++) {
E[A[i]].push_back({B[i], T[i]});
E[B[i]].push_back({A[i], T[i]});
}
vis.assign(n, 0);
v.assign(n, 0); u.assign(n, 0);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
cnt++;
dfsv(i); dfsu(i);
}
}
int mx = 0;
vector<int> mn(n, INT_MAX);
for (int i = 0; i < n; i++) {
mx = max({mx, v[i], u[i]});
mn[vis[i]] = min(mn[vis[i]], max(v[i], u[i]));
}
sort(mn.begin(), mn.end());
while (mn.back() == INT_MAX) mn.pop_back();
reverse(mn.begin(), mn.end());
set<int> s(vis.begin(), vis.end());
assert((int)s.size() == 2);
if (1 < (int)mn.size()) mx = max(mx, mn[0] + L + mn[1]);
if (2 < (int)mn.size()) mx = max(mx, mn[1] + (L << 1) + mn[2]);
return mx;
}
