#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
vector<pair<int,int>>v[maxn];
int pai[maxn], resp, val[maxn], at[maxn], cima[maxn], me;
pair<int,int> dp[maxn];
void dfs1(int u){
for(pair<int,int> p : v[u]){
int viz=p.first, w=p.second;
if(viz==pai[u]) continue;
pai[viz]=u;
dfs1(viz);
if(dp[viz].first+w>dp[u].first){
dp[u].second=dp[u].first;
dp[u].first=dp[viz].first+w;
}else if(dp[viz].first+w>dp[u].second) dp[u].second=dp[viz].first+w;
}
resp=max(resp,dp[u].first+dp[u].second);
val[u]=at[u]=dp[u].first;
}
void dfs2(int u){
if(pai[u]!=u){ // se n sou a raiz
at[u]=val[u]=max(dp[u].first,cima[u]);
}
me=min(me,val[u]);
for(pair<int,int> p : v[u]){
int viz=p.first, w=p.second;
if(viz==pai[u]) continue;
if(dp[u].first==dp[viz].first+w) at[u]=max(dp[u].second,cima[u]);
else at[u]=max(dp[u].first,cima[u]);
cima[viz]=at[u]+w;
dfs2(viz);
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
for(int i=0;i<m;i++){
A[i]++; B[i]++;
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
vector<int>process;
for(int i=1;i<=n;i++){
if(!pai[i]){
me=inf;
pai[i]=i;
dfs1(i);
dfs2(i);
if(me==inf) me=0;
process.push_back(me);
}
}
sort(process.begin(),process.end());
reverse(process.begin(),process.end());
if(process.size()==1) return max(process[0],resp);
if(process.size()==2) return max(process[0]+process[1]+l,resp);
if(process.size()>=3) return max({process[0]+process[1]+l,process[1]+process[2]+2*l,resp});
}
