#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> vec[100007];;
vector<int> group[100007];
vector<pair<int,int>> tans;
int mark[100007];
int dist[100007][3];
int grun=1;
int mxidx;
bool visited[100007];
void dfs(int x){
group[grun].push_back(x);
mark[x]=grun;
for(auto i:vec[x]){
if(!mark[i.first]){
dfs(i.first);
}
}
}
void bfs(int x,int channel){
for(auto i:group[mark[x]]){
dist[i][channel]=1e9;
visited[i]=0;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
while(!pq.empty()) pq.pop();
dist[x][channel]=0;
pq.push({0,x});
while(!pq.empty()){
int dis=pq.top().first;
int 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});
}
}
}
int 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=0;i<M;++i){
vec[A[i]].push_back({B[i],T[i]});
vec[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<N;++i){
if(!mark[i]){
dfs(i);
++grun;
}
}
for(int i=1;i<grun;++i){
bfs(group[i][0],0);
bfs(mxidx,1);
bfs(mxidx,2);
int mn=1e9,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});
}
if(tans.size()==2){
for(int i=0;i;++i){
mark[i]++;
++i;
}
}
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;
return 42;
}
