#include "dreaming.h"
// #include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <bitset>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define ln '\n'
const int N = 1e5 + 5;
const int INF = 1e9;
vector<pair<int, int>> adj[N];
int fir[N], sec[N], ans[N];
// int mn = INF, which = -1;
// vector<pair<int, int>> leader;
int mn = INF, mx = 0, final = 0;
vector<int> leader;
void dfs1(int u, int p){
for (auto& [e, v]: adj[u]){
if (v == p) continue;
dfs1(v, u);
if (fir[v] + e > fir[u]){
sec[u] = fir[u];
fir[u] = fir[v] + e;
} else if (fir[v] + e > sec[u]){
sec[u] = fir[v] + e;
}
}
}
void dfs2(int u, int p, int to_p){
ans[u] = max(to_p, fir[u]);
// if (ans[u] < mn){
// mn = ans[u];
// which = u;
// }
mn = min(mn, ans[u]);
mx = max(mx, ans[u]);
for (auto& [e, v]: adj[u]){
if (v == p) continue;
if (fir[v] + e == fir[u]){
dfs2(v, u, max(to_p, sec[u])+e);
} else dfs2(v, u, ans[u]+e);
}
}
void getLongestPath(int u){
dfs1(u, -1);
dfs2(u, -1, 0);
}
int travelTime(int NN, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++){
adj[A[i]].push_back({T[i], B[i]});
adj[B[i]].push_back({T[i], A[i]});
}
memset(ans, -1, sizeof(ans));
for (int i = 0; i < NN; i++){
if (ans[i] != -1) continue;
mn = INF; mx = 0;
getLongestPath(i); // tree rooted at i
// leader.push_back({mn, which});
final = max(final, mx);
leader.push_back(mn);
}
// for (int i = 0; i < NN; i++){
// cout << ans[i] << ' ';
// }
// cout << ln;
sort(leader.begin(), leader.end());
// for (auto& u: leader) cout << u << ' ';
// cout << ln;
int k = leader.size();
if (k == 1) return max(final, leader[k-1]);
if (k == 2) return max(final, leader[k-1] + leader[k-2] + L);
else return max(final, max(leader[k-1] + leader[k-2] + L,
leader[k-2] + leader[k-3] + 2*L));
}
