#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];
set<int,greater<int>>s;
vector<int> st;
int target,start;
vector<int> qs(N),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]});
}
// cout << en;
for(int i=0;i<n;i++){
if(!vis[i]){
// cout << "i" << i << sp;
mx=0,mxn=0,node=i,target=i;
dfs1(i,-1,0);
// cout << en;
// cout << i << sp << mxn << sp << node << en;
start=node;
dfs2(start,-1,0);
int trav=target;
// for(int i=0;i<n;i++)cout << par[i] << sp;
// cout << en;
st.push_back(0);
while (par[trav]!=-1)
{
// cout << trav << sp;
int weight=0;
for(auto [v,w]:adj[trav]){
if(v==par[trav]){
weight=w;
break;
}
}
st.push_back(weight);
trav=par[trav];
}
// cout << trav;
// cout << en;
for(int i=1;i<st.size();i++){
st[i]+=st[i-1];
// cout << st[i] << sp;
}
// cout << en;
// cout << target << sp << qs[st.size()-1] << en;
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());
// cout << "mi " << mi << en;
// if(mi==1e9)s.insert(0);
// else s.insert(mi);
s.insert(mi);
st.clear();
// cout << en;
}
}
// for(int i:s)cout << i << sp;
// int f1=q.top();
// q.pop();
// int f2=q.top();
int f1,f2;
if(s.size()==1){
return mxdia;
}
else if(s.size()==2){
f1=*s.begin(),f2=*next(s.begin());
return max(mxdia,f1+f2+l);
}
f1=*s.begin(),f2=*next(s.begin());
int f3=*next(next(s.begin()));
return max(mxdia,max(f1+f2+l,f2+f3+l*2 ) );
}
