#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN=1e5+1;
const int inf = 1e9;
int dp1[MAXN],up1[MAXN],visited[MAXN],diam,path;
vector<vector<pair<int,int>>> G(MAXN);
void dfs1(int v, int p){
visited[v]=1;
for(auto e: G[v]){
int u=e.first, w=e.second;
if(u==p) continue;
dfs1(u,v);
dp1[v]=max(dp1[v],dp1[u]+w);
diam=max(diam,dp1[v]);
}
}
void dfs2(int v, int p){
int idx1=-1,idx2=-1,best1=0,best2=0;
for(auto e: G[v]){
int u=e.first,w=e.second;
if(u==p) continue;
if(dp1[u]+w>=best1){
idx2=idx1;
best2=best1;
idx1=u;
best1=dp1[u]+w;
} else if(dp1[u]+w>=best2){
idx2=u;
best2=dp1[u]+w;
}
}
for(auto e: G[v]){
int u=e.first,w=e.second;
if(u==p) continue;
int best_child = (u!=idx1?best1:best2);
up1[u] = max(up1[v],best_child)+w;
diam = max(diam,max(up1[v]+best_child,best1+best2));
diam = max(diam,up1[u]);
dfs2(u,v);
}
}
void dfs3(int v, int p){
for(auto e: G[v]){
int u=e.first,w=e.second;
if(u==p) continue;
path=min(path,max(dp1[v],up1[v]));
dfs3(u,v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
int diameter=0,ans=0;
vector<int> components;
for(int i=0; i<=N; i++){
visited[i]=0;
G[i].clear();
dp1[i]=up1[i]=0;
}
for(int i=0; i<M; i++){
A[i]++;B[i]++;
G[A[i]].push_back({B[i],T[i]});
G[B[i]].push_back({A[i],T[i]});
}
for(int v=1; v<=N; v++){
if(!visited[v]){
diam=0,path=inf;
dfs1(v,0);
dfs2(v,0);
dfs3(v,0);
//if(v==2){cout << "xd " << path << "\n";}
diameter=max(diameter,diam);
if(path==inf)path=0;
components.push_back(path);
}
} // jak sie wypierdoli pozniej to ogarnij jak sa pojedyncze wierzcholki wliczane w odp czy cos bo to sie wypierdala chb
sort(components.begin(),components.end(), greater<>());
//for(int x: components) cout << x << " ";
//cout << "\n";
ans=max(components[0],diameter);
if(components.size()>=2){
ans=max(ans,components[0]+components[1]+L);
}
if(components.size()>=3){
ans=max(ans,components[1]+components[2]+2*L);
}
return ans;
}
