#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int inf = 1e9, N = 3e5 + 5;
vector <pii> v[N];
int lv[2][N], fix[N], cur_mx, vert, diam, rad, ans, a[N], b[N], c[N];
void dfs(int a, int p, int ty) {
fix[a] = 1;
if (lv[ty][a] > cur_mx) cur_mx = lv[ty][a], vert = a;
if (ty == 1) rad = min(rad, max(lv[ty][a], diam - lv[ty][a]));
for (pii sth : v[a]) {
int to = sth.f, c = sth.s;
if (to == p) continue;
if (ty == 1 && lv[0][to] != lv[0][a] - c) continue;
lv[ty][to] = lv[ty][a] + c;
dfs(to, a, ty);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n = N, m = M, l = L;
vector <int> vec;
for (int i = 0; i < m; i++) {
a[i] = A[i] + 1; b[i] = B[i] + 1; c[i] = T[i];
v[a[i]].pb({b[i], c[i]});
v[b[i]].pb({a[i], c[i]});
}
for (int i = 1; i <= n; i++) {
if (!fix[i]) { diam = 0;
cur_mx = -1; lv[0][i] = 0; dfs(i, 0, 0);
cur_mx = -1; lv[0][vert] = 0; dfs(vert, 0, 0); diam = cur_mx; ans = max(ans, diam);
cur_mx = -1; lv[1][vert] = 0; rad = inf; dfs(vert, 0, 1);
vec.pb(rad);
}
}
sort(vec.rbegin(), vec.rend());
if (vec.size() > 1) ans = max(ans, vec[0] + vec[1] + l);
if (vec.size() > 2) ans = max(ans, 2 * l + vec[1] + vec[2]);
return ans;
}
