#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
vector<pii> g[N];
int dp[N], pd[N];
void dfs(int v, int p, vector<bool> &vis){
vis[v] = 1;
dp[v] = 0;
for(auto [u, w]: g[v]){
if(u != p && !vis[u]){
dfs(u, v, vis);
dp[v] = max(dp[v], dp[u] + w);
}
}
}
void reroot(int v, int p, vector<bool> &vis, vi &C){
C.pb(v);
vis[v] = 1;
vector<int> pref, suf;
for(int j = 0; j < g[v].size(); ++j){
if(g[v][j].ff == p){
if(pref.size()) pref.pb(pref.back());
else pref.pb(0);
}else{
if(pref.size()) pref.pb(max(pref.back(), dp[g[v][j].ff] + g[v][j].ss));
else pref.pb(dp[g[v][j].ff] + g[v][j].ss);
}
}
for(int j = int(g[v].size())-1; j >= 0; --j){
if(g[v][j].ff == p){
if(suf.size()) suf.pb(suf.back());
else suf.pb(0);
}else{
if(suf.size()) suf.pb(max(suf.back(), dp[g[v][j].ff] + g[v][j].ss));
else suf.pb(dp[g[v][j].ff] + g[v][j].ss);
}
}
reverse(all(suf));
for(int j = 0; j < g[v].size(); ++j){
auto [u, w] = g[v][j];
if(u != p && !vis[u]){
pd[u] = max(pd[v] + w, max(j == 0 ? 0 : pref[j - 1], j + 1 == int(g[v].size()) ? 0 : suf[j + 1]) + w);
reroot(u, v, vis, C);
}
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for(int i = 0; i < m; ++i){
g[A[i]].pb({B[i], T[i]});
g[B[i]].pb({A[i], T[i]});
}
vector<bool> vis(n);
for(int i = 1; i <= n; ++i){
if(!vis[i-1]) dfs(i-1, i-1, vis);
}
vis.clear();
vis.resize(n, 0);
vector<int> val;
for(int i = 1; i <= n; ++i){
if(!vis[i-1]) {
pd[i - 1] = 0;
vi C;
reroot(i-1, i-1, vis, C);
int mn = MOD;
for(int u: C){
mn = min(mn, max(dp[u], pd[u]));
}
val.pb(mn);
}
}
int ans = 0;
for(int c: val) ans=max(c, ans);
if(val.size() == 1){
return val[0];
}
sort(all(val));
ans = max(ans, val.back() + val[int(val.size())-2] + L);
if(val.size()>=3)
ans = max(ans, val[int(val.size())-2] + val[int(val.size())-3] + 2*L);
return ans;
}
