#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr int maxn=1e5 + 5;
vector<pair<int,int>> t[maxn];
bool vis[maxn];
int spojna[maxn];
long long dp1[maxn],dp2[maxn]; //najdluzsza, druga najdluzsza
long long dp3[maxn]; //najdluzsza ale w gore
long long spojnamin[maxn];
void dfs1(int v,int nr){
vis[v]=true;
spojna[v]=nr;
for (auto [u,w]:t[v]){
if (vis[u]) continue;
dfs1(u,nr);
if (dp1[u]+w > dp1[v]){
dp2[v]=dp1[v];
dp1[v]=dp1[u]+w;
} else if (dp1[u]+w>dp2[v]){
dp2[v]=dp1[u]+w;
}
}
}
void dfs2(int v,long long sofar){
vis[v]=true;
dp3[v]=sofar;
for (auto [u,w]:t[v]){
if (vis[u]) continue;
if (dp1[u]+w==dp1[v]) dfs2(u,max(dp2[v],sofar)+w);
else dfs2(u,max(sofar,dp1[v])+w);
}
}
int travelTime(int n,int m,int l,int A[],int B[],int T[]){
for (int i=1;i<=n;i++){
t[i].clear();
dp1[i]=0,dp2[i]=0,dp3[i]=0;
spojnamin[i]=2e18;
vis[i]=false;
spojna[i]=0;
}
for (int i=0;i<m;i++){
t[A[i]+1].push_back({B[i]+1,T[i]});
t[B[i]+1].push_back({A[i]+1,T[i]});
}
int nr=1;
for (int i=1;i<=n;i++){
if (!vis[i]) dfs1(i,nr++);
}
//for (int i=1;i<=n;i++) cout<<i-1<<": "<<dp1[i]<<" "<<dp2[i]<<"\n";
long long ans=0;
for (int i=1;i<=n;i++){
ans=max(ans,dp1[i]+dp2[i]);
vis[i]=false;
}
for (int i=1;i<=n;i++){
if (!vis[i]) dfs2(i,0);
}
for (int i=1;i<=n;i++) spojnamin[spojna[i]]=min(spojnamin[spojna[i]],max(dp1[i],dp3[i]));
vector<long long> v;
for (int i=1;i<nr;i++) v.push_back(spojnamin[i]);
sort(v.rbegin(),v.rend());
if (v.size()>=2) ans=max(ans,v[0]+v[1]+l);
if (v.size()>=3) ans=max(ans,v[1]+v[2]+2*l);
//for (int i=1;i<=n;i++) cout<<i-1<<": "<<dp1[i]<<" "<<dp3[i]<<"\n";
return ans;
}
