#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define en '\n'
#define sp ' '
typedef long long ll;
#define pii pair<int,int>
const int N=1e5+10;
vector<pii> adj[N];
vector<int> st,ans;
int target,start;
vector<int> par(N);
vector<int> vis(N);
int mx,mxn,node;
int mxdia;
void dfs1(int u,int p,int nw){
vis[u]=1;
// cout << u << sp;
if(mxn<nw){
mxn=nw;
node=u;
}
for(auto [v,w]:adj[u]){
if(v==p)continue;
dfs1(v,u,nw+w);
}
return ;
}
void dfs2(int u,int p,int nw){
par[u]=p;
// cout << 's' << u << sp <<p << en;
if(mx<nw){
mx=nw;
target=u;
}
for(auto [v,w]:adj[u]){
if(v==p)continue;
dfs2(v,u,nw+w);
}
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({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
for(int i=0;i<n;i++){
if(!vis[i]){
mx=0,mxn=0,node=i,target=i;
dfs1(i,-1,0);
start=node;
dfs2(start,-1,0);
int trav=target;
st.push_back(0);
while (par[trav]!=-1)
{
int weight=0;
for(auto [v,w]:adj[trav]){
if(v==par[trav]){
weight=w+st.back();
break;
}
}
st.push_back(weight);
trav=par[trav];
}
int mi=1e9;
for(int i=0;i<st.size();i++){
mi=min(mi,max(st[i],st.back()-st[i]));
}
mxdia=max(mxdia,st.back());
ans.push_back(mi);
st.clear();
}
}
sort(ans.begin(),ans.end(),greater<int>());
if(ans.size()==1){
return mxdia;
}
else if(ans.size()==2){
return max(mxdia,ans[0]+ans[1]+l);
}
return max(mxdia,max(ans[0]+ans[1]+l,ans[1]+ans[2]+l*2 ) );
}
