#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
vector<bool> vis;
vector<vector<pair<int, int>>> adj;
vector<int> fir, sec, ans;
void dfsIn(int node, int parent = -1) {
for (auto &[child, weight] : adj[node]) {
if (child == parent) continue;
dfsIn(child, node);
if (fir[child] + weight > fir[node]) {
sec[node] = fir[node];
fir[node] = fir[child] + weight;
}
else if (fir[child] + weight > sec[node]) {
sec[node] = fir[child] + weight;
}
}
}
int dfsOut(int node, int dist = 0) {
vis[node] = true;
int best;
best = ans[node] = max(dist, fir[node]);
for (auto &[child, weight] : adj[node]) {
if (vis[child]) continue;
if (fir[child] + weight == fir[node]) {
best = min(best, dfsOut(child, max(dist, sec[node]) + weight));
}
else {
best = min(best, dfsOut(child, ans[node] + weight));
}
}
return best;
}
int handleConnectedComponent(int node) {
dfsIn(node);
return dfsOut(node);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vis.assign(N, false);
adj.resize(N);
fir.assign(N, 0);
sec.assign(N, 0);
ans.resize(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> candidates;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
candidates.push_back(handleConnectedComponent(i));
}
}
sort(candidates.rbegin(), candidates.rend());
if (candidates.size() == 1) {
return candidates[0];
}
else if (candidates.size() == 2) {
return candidates[0] + candidates[1] + L;
}
else {
return max(
candidates[0] + candidates[1] + L,
candidates[1] + candidates[2] + L + L
);
}
}
// void solution() {
// int N, M, L; cin >> N >> M >> L;
// int A[M], B[M], T[M];
// for (int i = 0; i < M; i++) {
// cin >> A[i] >> B[i] >> T[i];
// }
// cout << travelTime(N, M, L, A, B, T) << endl;
// }
// signed main() {
// solution();
// }
