#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, long long>>> 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]});
}
vector<bool> vis(N, 0);
vector<long long> depth(N);
vector<vector<pair<long long, int>>> mxu(N);
function<void(int, int, vector<int> &)> dfs = [&](int a, int p, vector<int> &curr) {
vis[a] = 1;
for (auto x : adj[a]) {
if (x.first == p) continue;
depth[x.first] = depth[a]+x.second;
dfs(x.first, a, curr);
mxu[a].push_back({mxu[x.first][0].first+x.second, x.first});
}
sort(mxu[a].rbegin(), mxu[a].rend());
mxu[a].push_back({0, -1});
curr.push_back(a);
};
function<long long(int, int, long long)> agg = [&](int a, int p, long long sum) -> long long {
long long best = max(mxu[a][0].first, sum);
for (auto x : adj[a]) {
if (x.first == p) continue;
long long aus = (mxu[a][0].second == x.first) ? mxu[a][1].first : mxu[a][0].first;
aus = max(aus, best)+x.second;
best = min(best, agg(x.first, a, aus));
}
return best;
};
vector<long long> md;
long long f = 0;
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
depth[i] = 0;
vector<int> r;
dfs(i, -1, r);
md.push_back(agg(i, -1, 0));
int dm = i;
for (int x : r) {
if (depth[dm] < depth[x]) dm = x;
}
r.clear();
depth[dm] = 0;
dfs(dm, -1, r);
for (int x : r) {
if (depth[dm] < depth[x]) dm = x;
}
f = max(depth[dm], f);
}
sort(md.rbegin(), md.rend());
if (md.size() > 1) f = max(f, md[0]+md[1]+L);
if (md.size() > 2) f = max(f, md[1]+md[2]+2*L);
return f;
}
