#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
const int INF = 2e9;
const int mxN = 1e5 + 5000;
vector<pair<int,int>> adj[mxN];
int down_dp[mxN],up_dp[mxN],dp[mxN],vis[mxN],cost1=0,cost2=0,grp=1;
vector<int> group_max(mxN,INF),group_max_node(mxN,0);
void dfs(int u,int par){
vis[u]=grp;
for(auto it:adj[u]){
if(it.fi==par) continue;
dfs(it.fi,u);
down_dp[u]=max(down_dp[u],down_dp[it.fi]+it.se);
}
}
void reroot(int u,int par){
int c[2]; pair<int,int> p;
p.fi=p.se=-1;
c[0]=c[1]=0;
dp[u]=max(dp[u],down_dp[u]);
for(auto it:adj[u]){
if(it.fi!=par){
if(p.fi==-1) p.fi=it.fi,c[0]=it.se;
else if(down_dp[p.fi]+c[0]<down_dp[it.fi]+it.se){
swap(p.fi,p.se);
swap(c[0],c[1]);
c[0]=it.se;
p.fi=it.fi;
}else if(down_dp[p.se]+c[1]<down_dp[it.fi]+it.se){
p.se=it.fi;
c[1]=it.se;
}
}
}
for(auto it:adj[u]){
if(it.fi^par){
up_dp[it.fi]=up_dp[u]+it.se;
if(it.fi==p.fi&&p.fi==-1) up_dp[it.fi]=0;
else if(it.fi==p.fi) up_dp[it.fi]=max(up_dp[it.fi],down_dp[p.se]+c[1]+it.se);
else up_dp[it.fi]=max(up_dp[it.fi],down_dp[p.fi]+c[0]+it.se);
dp[it.fi]=max(up_dp[it.fi],down_dp[it.fi]);
reroot(it.fi,u);
}
}
cost1=max(cost1,dp[u]);
}
pair<int,int> max_dist(int u,int par,int w){
pair<int,int> ans={w,u};
for(auto it:adj[u]){
if(it.fi!=par){
ans=max(ans,max_dist(it.fi,u,w+it.se));
}
}
return ans;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i<M;++i){
adj[A[i]].pb({B[i],T[i]});
adj[B[i]].pb({A[i],T[i]});
}
for(int i=0;i<N;++i){
if(vis[i]==0){
dfs(i,-1);
reroot(i,-1);
++grp;
}
}
for(int i=0;i<N;++i){
if(group_max[vis[i]]>dp[i]){
group_max[vis[i]]=dp[i];
group_max_node[vis[i]]=i;
}
}
for(int i=2;i<grp;++i){
adj[group_max_node[i-1]].pb({group_max_node[i],L});
adj[group_max_node[i]].pb({group_max_node[i-1],L});
}
pair<int,int> p1=max_dist(0,-1,0);
pair<int,int> p2=max_dist(p1.se,-1,0);
return max(cost1,group_max[1]+group_max[2]+L);
}
