#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,long long>> vec[100007];;
vector<long long> group[100007];
vector<pair<long long,long long>> tans;
long long mark[100007];
long long dist[100007][3];
long long grun;
long long mxidx;
bool visited[100007];
void dfs(long long x){
group[grun].push_back(x);
mark[x]=grun;
for(auto i:vec[x]){
if(!mark[i.first]){
dfs(i.first);
}
}
}
void bfs(long long x,long long channel){
for(auto i:group[mark[x]]){
dist[i][channel]=1e18;
visited[i]=0;
}
priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
while(!pq.empty()) pq.pop();
dist[x][channel]=0;
pq.push({0,x});
while(!pq.empty()){
long long dis=pq.top().first;
long long node=pq.top().second;
pq.pop();
for(auto i:vec[node]){
if(dis+i.second<dist[i.first][channel]){
dist[i.first][channel]=dis+i.second;
pq.push({dist[i.first][channel],i.first});
}
}
}
long long mx=0;
for(auto i:group[mark[x]]){
if(dist[i][channel]>mx){
mx=dist[i][channel];
mxidx=i;
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=1;i<=N;++i){
vec[i].clear();
group[i].clear();
mark[i]=0;
grun=1;
visited[i]=0;
dist[i][0]=dist[i][1]=dist[i][2]=0;
}
tans.clear();
for(long long i=0;i<M;++i){
vec[A[i]].push_back({B[i],T[i]});
vec[B[i]].push_back({A[i],T[i]});
}
for(long long i=1;i<=N;++i){
if(!mark[i]){
dfs(i);
++grun;
}
}
for(long long i=1;i<grun;++i){
bfs(group[i][0],0);
bfs(mxidx,1);
bfs(mxidx,2);
long long mn=1e18,mnidx;
for(auto j:group[i]){
if(max({dist[j][0],dist[j][1],dist[j][2]})<mn){
mn=max({dist[j][0],dist[j][1],dist[j][2]});
mnidx=j;
}
}
tans.push_back({mn,mnidx});
}
sort(tans.begin(),tans.end());
reverse(tans.begin(),tans.end());
if(tans.size()==1) return tans[0].first;
else return tans[0].first+L+tans[1].first;
}
