#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[100001];
long long lon[100001] ,vis[100001];
void dfs(int i){
lon[i] = 0;
vis[i] = 1;
for(auto j:adj[i]){
if(vis[j.first]==0){
dfs(j.first);
lon[i] = max(lon[j.first]+j.second,lon[i]);
}
}
}
long long pref[100001],suf[100001];
long long mi = 1e18 , ma = 1e18;
void reroot(int i,int pr,long long cnt){
mi = min(mi,max(cnt,lon[i]));
ma = max(ma,max(cnt,lon[i]));
long long maa = cnt;
for(auto j:adj[i]){
if(j.first==pr)continue;
pref[j.first] = maa;
maa = max(maa,lon[j.first]+j.second);
}
reverse(adj[i].begin(),adj[i].end());
maa = cnt;
for(auto j:adj[i]){
if(j.first==pr)continue;
suf[j.first] = maa;
maa = max(maa,lon[j.first]+j.second);
}
reverse(adj[i].begin(),adj[i].end());
for(auto j:adj[i]){
if(j.first==pr)continue;
reroot(j.first,i,max(pref[j.first],suf[j.first])+j.second);
}
}
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]});
}
vector<long long> v;
long long ans = 0;
for(int i = 0;i<N;i++){
if(vis[i])continue;
dfs(i);
mi = 1e18;
ma = 0;
reroot(i,0,0);
v.push_back(mi);
ans = max(ans,ma);
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if(v.size()>1)ans = max(ans,v[0]+v[1]+L);
if(v.size()>2)ans = max(ans,v[1]+v[2]+2*L);
return ans;
}
/*
int main(){
int N = 12 , M = 8 , L = 2;
int A[] = {0,8,2,5,5,1,1,10};
int B[] = {8,2,7,11,1,3,9,6};
int T[] = {4,2,4,3,7,1,5,3};
cout<<travelTime(N,M,L,A,B,T)<<endl;
}
*/
