/* 11.09.2025 */
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
#define F first
#define S second
vector<vector<pair<int,int>>> adj;
vector<pair<int,int>> dp1,dp2,path;
vector<int> pt,used;
void dfs1(int v,int e){
used[v]=1;
pt.push_back(v);
for(auto &u:adj[v]){
if(u.F==e)continue;
dfs1(u.F,v);
int val=dp1[u.F].F+u.S;
if(val>=dp1[v].F){
dp2[v]=dp1[v];
dp1[v]={val,u.F};
}else if(val>=dp2[v].F){
dp2[v]={val,u.F};
}
}
}
void dfs2(int v,int e){
for(auto &u:adj[v]){
if(u.F==e)continue;
int val;
if(u.F==dp1[v].S)val=dp2[v].F+u.S;
else val=dp1[v].F+u.S;
if(val>=dp1[u.F].F){
dp2[u.F]=dp1[u.F];
dp1[u.F]={val,v};
}else if(val>=dp2[u.F].F){
dp2[u.F]={val,v};
}
dfs2(u.F,v);
}
}
void init(int pos){
pt.clear();
dfs1(pos,-1);
dfs2(pos,-1);
int mx=0;
for(auto v:pt){
mx=max(mx,dp1[v].F+dp2[v].F);
}
int idx=-1;
int mn=INT_MAX;
for(auto v:pt){
int val=dp1[v].F+dp2[v].F;
if(val==mx){
int x=max(dp1[v].F,dp2[v].F);
if(x<mn){
mn=x;
idx=v;
}
}
}
path.push_back({mn,idx});
}
int travelTime(int N,int M,int L,int a[],int b[],int t[]){
adj.assign(N,vector<pair<int,int>>());
dp1.assign(N,{0,-1});
dp2.assign(N,{0,-1});
used.assign(N,0);
path.clear();
for(int i=0;i<M;i++){
int x=a[i],y=b[i];
ll z=t[i];
adj[x].push_back({y,z});
adj[y].push_back({x,z});
}
for(int i=0;i<N;i++){
if(!used[i])init(i);
}
sort(path.begin(),path.end(),greater<pair<int,int>>());
for(int i=1;i<path.size();i++){
int x=path[i].S,y=path[0].S;
adj[x].push_back({y,(ll)L});
adj[y].push_back({x,(ll)L});
}
for(int i=0;i<N;i++){
dp1[i]=dp2[i]={0,-1};
}
pt.clear();
dfs1(0,-1);
dfs2(0,-1);
int mx=0;
for(int i=0;i<N;i++) mx=max(mx,dp1[i].F);
return mx;
}
