#include "dreaming.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,int>
using namespace std;
const int N=1e5+1;
ll a,adis,b,bdis,c,cdis;
ll dis[N],rdis[N];
bool chk;
bitset<N>vis;
vector<pii>adj[N];
vector<int>center;
bool comp(int a,int b){
return rdis[a]>rdis[b];
}
void dfs1(int u,int p,bool boo){
vis[u]=true;
if(!boo&&dis[u]>adis){
a=u;
adis=dis[u];
}
else if(boo&&dis[u]>bdis){
b=u;
bdis=dis[u];
}
for(pii wv:adj[u]){
ll w=wv.first;
int v=wv.second;
if(v==p)continue;
dis[v]=dis[u]+w;
dfs1(v,u,boo);
}
}
void dfs2(int u,int p){
if(u==a){
chk=true;
c=u;
cdis=bdis;
return ;
}
for(pii wv:adj[u]){
int v=wv.second;
if(v==p)continue;
dfs2(v,u);
if(chk){
if(max(dis[u],bdis-dis[u])<cdis){
c=u;
cdis=max(dis[u],bdis-dis[u]);
}
return ;
}
}
}
int travelTime(int N, 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]});
}
ll mx=0,smx=0,tmx=0,mxb=0;
for(int i=0; i<N; i++){
if(vis[i])continue;
a=i;
adis=0,bdis=0;
chk=false;
dis[i]=0;
dfs1(i,-1,0);
dis[a]=0;
b=a,c=a;
dfs1(a,-1,1);
dfs2(b,-1);
center.push_back(c);
rdis[c]=cdis;
}
sort(center.begin(),center.end(),comp);
for(int i=1; i<center.size(); i++){
adj[center[i]].push_back({L,center[0]});
adj[center[0]].push_back({L,center[i]});
}
dis[0]=0;
adis=0,bdis=0,a=0;
dfs1(0,-1,0);
b=a;
dis[a]=0;
dfs1(a,-1,1);
return bdis;
}
