#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
struct Info {
int a, ta, coa;
int b, tb, cob;
};
Info sv[101010];
vector<pair<int, int> > g[101010];
bool used[101010];
void dfs(int v, int pred) {
used[v] = true;
sv[v] = {0, v, 0, 0, v, 0};
for (auto [to, c] : g[v]) {
if (to == pred)continue;
dfs(to, v);
if (sv[v].a < sv[to].a + c) {
sv[v].b = sv[v].a;
sv[v].tb = sv[v].ta;
sv[v].cob = sv[v].coa;
sv[v].a = sv[to].a + c;
sv[v].ta = to;
sv[v].coa = c;
} else if (sv[v].b < sv[to].a + c) {
sv[v].b = sv[to].a + c;
sv[v].tb = to;
sv[v].cob = c;
}
}
// cout << v-1 << " --- " << sv[v].a << " " << sv[v].ta-1 << " ;; " << sv[v].b << " " << sv[v].tb-1 << endl;
}
int MX = 1010101010;
void psh(int v, int val) {
MX = min(MX, max({val, sv[v].a, sv[v].b}));
if (max({val, sv[v].a, sv[v].b}) <=
max({max(val, sv[v].b) + sv[v].coa, sv[sv[v].ta].a, sv[sv[v].ta].b}))return;
psh(sv[v].ta, max(val, sv[v].b) + sv[v].coa);
}
int f, s, t;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 1; i <= M; i++) {
g[A[i - 1] + 1].push_back({B[i - 1] + 1, T[i - 1]});
g[B[i - 1] + 1].push_back({A[i - 1] + 1, T[i - 1]});
}
for (int i = 1; i <= N; i++) {
if (used[i])continue;
dfs(i, i);
MX = 1010101010;
psh(i, 0);
if (f < MX) {
t = s;
s = f;
f = MX;
} else if (s < MX) {
t = s;
s = MX;
} else if (t < MX) {
t = MX;
}
// cout << endl;
}
if (M == N - 1)return f;
if (M == N - 2)return f + s + L;
return max(f + L + s, t + L + L + s);
}
