#include "dreaming.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int MAX = 100007;
int V[2][MAX], D[2][MAX];
vector<pii> G[MAX];
vector<int> C;
int DFS(int cur, int c) {
int ret = cur;
V[c][cur] = 1;
for (auto [next, nd] : G[cur]) {
if (V[c][next]) continue;
D[c][next] = D[c][cur] + nd;
int d = DFS(next, c);
if (D[c][d] > D[c][ret]) ret = d;
}
return ret;
}
int travelTime(int N, int M, int L, int* A, int* B, int* T) {
for (int i = 0; i < M; ++i) {
G[A[i]].emplace_back(B[i], T[i]);
G[B[i]].emplace_back(A[i], T[i]);
}
int rad = 0;
memset(D, 0x3f, sizeof(D));
for (int i = 0; i < N; ++i) {
if (V[0][i]) continue;
D[0][i] = 0;
int d1 = DFS(i, 0);
D[1][d1] = 0;
int d2 = DFS(d1, 1);
int hd = 2e9, d = D[1][d2];
rad = max(d, rad);
while (d2 != d1) {
for (auto [prev, pd] : G[d2]) {
if (D[1][prev] + pd != D[1][d2]) continue;
d2 = prev;
break;
}
hd = min(hd, max(D[1][d2], d - D[1][d2]));
}
hd = min(hd, d);
C.push_back(hd);
}
sort(C.begin(), C.end(), greater<int>());
if (C.size() == 1) return max(rad, C[0]);
else if (C.size() == 2) return max(rad, C[0] + C[1] + L);
return max({rad, C[0] + C[1] + L, C[1] + C[2] + L * 2});
}
