#include "dreaming.h"
#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long int
#define pb push_back
using namespace std;
const int N=1e5+7;
vector<pair<int,int> > adj[N];
bool vis[N];
int d[N];
int par[N];
int c[N];
int mx;
int start=-1,tok=-1;
void dfs(int u,int p,int l){
vis[u]=1;
for(auto v:adj[u]) {
if(v.f==p) {
continue;
}
dfs(v.f,u,l+v.s);
}
if(l>mx) {
mx=l;
start=u;
}
}
void dfs2(int u,int p,int l){
vis[u]=1;
for(auto v:adj[u]) {
if(v.f==p) {
continue;
}
par[v.f]=u;
d[v.f]=d[u]+v.s;
dfs2(v.f,u,l+v.s);
}
if(l>mx) {
mx=l;
tok=u;
}
}
int radius(int u,int p){
//memset(par,-1,sizeof par);
mx=0;
start=-1; tok=-1;
dfs(u,p,0);
mx=0;
if(start==-1) {
return 0;
}
dfs2(start,p,0);
int diameter=mx;
int ans=1e9;
for(int u=tok; u!=start; u=par[u]) {
//cout<<u<<" "<<d[u]<<endl;
ans=min(ans,max(diameter-d[u],d[u]));
}
// cout<<ans<<endl;
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n=N;
int m=M;
int l=L;
for(int i=0; i<M; i++) {
int u=A[i];
int v=B[i];
int w=T[i];
adj[u].pb({v,w});
adj[v].pb({u,w});
}
int cnt=1;
for(int i=0; i<n; i++) {
if(!vis[i]) {
vis[i]=1;
//dfs(i,-1,0);
c[cnt]=radius(i,-1);
cnt++;
}
}
int mx1=0;
int mx2=0;
for(int i=1; i<cnt; i++) {
if(c[i]>mx1) {
mx2=mx1;
mx1=c[i];
}
else if(c[i]>mx2) {
mx2=c[i];
}
}
int lol=mx1+mx2+l;
return lol;
}
