#include "dreaming.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
//int N, M, L, A[100005], B[100005], T[100005];
int p[100005], d[100005], ans=0;
int find(int s){
if (s==p[s])return s;
return p[s]=find(p[s]);
}
void Union_find(int x, int y){
int z=find(x), t=find(y);
p[max(z, t)]=min(z, t);
}
vector<pair<int, int> >adj[100005];
vector<int>x[100005];
vector<int>y;
int mx_d[100005]={0}, sec[100005]={0};
bool is[100005]={0};
void dfs(int u, int par){
p[u]=par;
for (int i=0;i<adj[u].size();i++){
int v=adj[u][i].ff;
if (v==par)continue;
dfs(v, u);
if (mx_d[u]<mx_d[v]+adj[u][i].ss){
mx_d[u]=mx_d[v]+adj[u][i].ss;
is[u]=0;
continue;
}
if (mx_d[u]==mx_d[v]+adj[u][i].ss){
is[u]=1;
}
}
if (is[u])sec[u]=mx_d[u];
for (int i=0;i<adj[u].size();i++){
int v=adj[u][i].ff;
if (v!=par && mx_d[u]!=mx_d[v]+adj[u][i].ss)sec[u]=max(sec[u], mx_d[v]+adj[u][i].ss);
}
ans=max(ans, mx_d[u]+sec[u]);
}
void solve(int s, int u, int dis){
d[s]=min(d[s], max(dis, mx_d[u]));
for (int i=0;i<adj[u].size();i++){
int v=adj[u][i].ff;
if (v==p[u])continue;
if (mx_d[v]+adj[u][i].ss==mx_d[u])solve(s, v, max(dis, sec[u])+adj[u][i].ss);
else solve(s, v, max(dis, mx_d[u])+adj[u][i].ss);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(mx_d, 0, sizeof(mx_d));
if (N==1)return 0;
if (N==2){
if (M==1)return T[0];
else return L;
}
for (int i=0;i<N;i++)p[i]=i;
for (int i=0;i<M;i++){
Union_find(A[i], B[i]);
adj[A[i]].pb(mp(B[i], T[i]));
adj[B[i]].pb(mp(A[i], T[i]));
}
for (int i=0;i<N;i++){
x[find(i)].pb(i);
}
for (int i=0;i<N;i++){
if (x[i].empty())continue;
y=x[i];
dfs(y[0], y[0]);
d[i]=mx_d[y[0]];
for (int j=0;j<adj[y[0]].size();j++){
if (mx_d[adj[y[0]][j].ff]+adj[y[0]][j].ss==mx_d[y[0]]){
solve(i, adj[y[0]][j].ff, sec[y[0]]+adj[y[0]][j].ss);
}
else solve(i, adj[y[0]][j].ff, mx_d[y[0]]+adj[y[0]][j].ss);
}
}
sort(d, d+N);
if (M==N-1)return ans;
if (M==N-2)return max(ans, d[N-1]+d[N-2]+L);
return max(ans, max(d[N-1]+d[N-2]+L, d[N-2]+d[N-3]+2*L));
}
