#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; i++) adj[A[i]].push_back({B[i], T[i]}), adj[B[i]].push_back({A[i], T[i]});
int mxd = 0, mxu = 0;
vector<int> seen(n), comp;
vector<vector<int>> ds(2, vector<int>(n));
auto dfs1 = [&](int id, auto dfs, int u, int p = -1, int d = 0) -> void {
if (mxd < d) mxd = d, mxu = u;
ds[id][u] = d;
seen[u] = 1;
comp.push_back(u);
for (auto [v, l] : adj[u]) if (v != p) dfs(id, dfs, v, u, d+l);
};
vector<int> diam, rad;
int ans = 0;
for (int i = 0; i < n; i++) if (!seen[i]) {
mxd = 0, mxu = i;
dfs1(0, dfs1, i);
mxd = 0;
int a = mxu;
dfs1(0, dfs1, a);
comp.clear();
int b = mxu;
dfs1(1, dfs1, b);
ans = max(ans, mxd);
diam.push_back(mxd);
int r = n, dab = ds[1][a];
for (int u : comp) if (ds[0][u]+ds[1][u] == dab) r = min(r, max(ds[0][u], ds[1][u]));
rad.push_back(r);
}
sort(rad.rbegin(), rad.rend());
for (int i = 1; i < rad.size(); i++) ans = max(ans, rad[0]+rad[i]+L);
for (int i = 2; i < rad.size(); i++) ans = max(ans, rad[1]+rad[i]+2*L);
return ans;
}
