#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
const int MX = 1e5+5;
const int INF = 1e9+1e8;
vector<in> adj[MX];
vector<array<int, 4>> rec[MX];
int dp[MX];
int dp2[MX];
vector<int> vis;
void dfs(int u, int p)
{
dp[u] = 0;
vis[u] = 1;
for(auto [v, w]: adj[u])
{
if(v==p) continue;
dfs(v, u);
dp[u] = max(dp[v]+w, dp[u]);
rec[u].pb({v, w, dp[u], dp[v]+w});
}
int s = -INF;
int N = rec[u].size();
for(int i = N-1; i >= 0; i--)
{
s = max(s, rec[u][i][3]);
rec[u][i][3] = max(s, rec[u][i][3]);
}
return;
}
void dfs2(int u, int p, int CR, int &mn, int &mx)
{
dp2[u] = max(dp[u], CR);
mn = min(mn, dp2[u]);
mx = max(mx, dp2[u]);
if(rec[u].empty())
return;
int N = rec[u].size();
for(int i = 0; i < N; i++)
{
int v = rec[u][i][0];
int s = CR;
if((i > 0))
s = max(s, rec[u][i-1][2]);
if((i < (N-1)))
s = max(s, rec[u][i+1][3]);
dfs2(v, u, s+rec[u][i][1], mn, mx);
}
return;
}
int travelTime(int n, int m, int L, int a[], int b[], int t[])
{
for(int i = 0; i < n; i++)
{
adj[i].clear();
rec[i].clear();
}
vis.assign(n, 0);
for(int i = 0; i < m; i++)
{
adj[a[i]].pb({b[i], t[i]});
adj[b[i]].pb({a[i], t[i]});
}
vector<int> v;
int ANS = 0;
for(int i = 0; i < n; i++)
{
if(vis[i])
continue;
int mn = INF;
int mx = -INF;
dfs(i, -1);
dfs2(i, -1, 0, mn, mx);
ANS = max(ANS, mx);
v.pb(mn);
if(v.size() == 4)
{
sort(v.rbegin(), v.rend());
v.pob();
}
}
if(v.size() == 1)
return ANS;
ANS = max(ANS, L+v[0]+v[1]);
if(v.size() < 3)
return ANS;
ANS = max(ANS, 2*L+v[1]+v[2]);
return ANS;
}
