#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> dp;
vector<vector<pair<int, int>>> g;
vector<int> d;
vector<int> h;
void dfs(int k, int p){
d[k] = 1;
for(int y = 0; y < g[k].size(); y++){
if(g[k][y].first == p) continue;
dfs(g[k][y].first, k);
dp[k] = max(dp[k], dp[g[k][y].first]+g[k][y].second);
}
}
int m = 2e9;
int mmx = 0;
void reroot(int k, int p, int up){
int mx = 0;
int mx1 = 0;
for(int y = 0; y < g[k].size(); y++){
if(g[k][y].first == p) continue;
if(mx < dp[g[k][y].first] + g[k][y].second){
mx1 = mx;
mx = dp[g[k][y].first] + g[k][y].second;
}else{
mx1 = max(mx1, dp[g[k][y].first] + g[k][y].second);
}
}
h[k] = max(dp[k], up);
for(int y = 0; y < g[k].size(); y++){
if(g[k][y].first == p) continue;
if(mx == dp[g[k][y].first]+g[k][y].second){
reroot(g[k][y].first, k, max(mx1, up)+g[k][y].second);
}else{
reroot(g[k][y].first, k, max(mx, up)+g[k][y].second);
}
}
mmx = max(mmx, h[k]);
m = min(m, h[k]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
g.resize(N+1);
for(int i = 0; i < M; i++){
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
int mn = 0;
d.resize(N);
h.resize(N);
dp.resize(N);
multiset<int> s;
for(int i = 0; i < N; i++){
if(d[i] == 1) continue;
m = 1e9;
dfs(i, -1);
reroot(i, -1, 0);
d[i] = -m;
// cout << m << "\n";
s.insert(m+L);
}
for(int i = 0; i < N; i++){
if(d[i] == 1) continue;
s.erase(s.find(-d[i]+L));
if(s.size() >= 2){
auto it = s.rbegin();
auto it1 = it;
it1++;
mn = max(*it + *it1, *it - d[i]);
}else if(s.size() >= 1){
mn = -d[i] + *s.rbegin();
}
s.insert(-d[i]+L);
}
// cout << mn << " " << mmx << endl;
return max(mn, mmx);
}
