#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<array<int, 2>>> 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<int> d0(N, 1e9), d1(N, 1e9), d2(N, 1e9);
vector<bool> v0(N, false), v1(N, false), v2(N, false), vf(N, false);
auto dijkstra = [N, &adj] (int i, vector<int> &distance, vector<bool> &visited) -> int {
priority_queue<array<int, 2>> q;
q.push({0, i}); distance[i] = 0;
int x = i;
while (!q.empty()) {
auto [_, v] = q.top(); q.pop();
if (visited[v]) continue;
if (distance[v] > distance[x]) x = v;
visited[v] = true;
for (auto [u, w]: adj[v]) {
if (distance[v] + w < distance[u]) {
distance[u] = distance[v] + w;
q.push({-distance[u], u});
}
}
}
return x;
};
auto find_center = [N, &adj, &d1, &d2, &vf] (int i) -> int {
queue<int> q;
vf[i] = true; q.push(i);
int x = i;
while(!q.empty()) {
int v = q.front(); q.pop();
for (auto [u, _]: adj[v]) {
if (vf[u]) continue;
if (max(d1[u], d2[u]) < max(d1[x], d2[x])) x = u;
vf[u] = true;
q.push(u);
}
}
return x;
};
int res = 0;
int e1 = -L, e2 = -L;
for (int i = 0; i < N; i++) {
if (vf[i]) continue;
int a = dijkstra(i, d0, v0);
int b = dijkstra(a, d1, v1);
dijkstra(b, d2, v2);
res = max(res, d1[b]);
int c = find_center(i);
int e = max(d1[c], d2[c]);
if (e > e1) {
e2 = e1;
e1 = e;
}
else if (e > e2) {
e2 = e;
}
}
res = max(res, e1 + e2 + L);
return res;
}
