#include "dreaming.h"
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define max_N 100010
vector<pair<int, int> > Graph[max_N];
vector<int> Radius;
int Dist[max_N],Chk[max_N];
int FindEnd(int start, int chked)
{
queue<int> Q; int i,x,y,far,ind;
Q.push(start); Dist[start] = 0; Chk[start] = chked;
far = 0; ind = start;
while (!Q.empty()){
x = Q.front(); Q.pop();
for (i=0;i<Graph[x].size();i++){
y = Graph[x][i].first;
if (Chk[y] != chked){
Q.push(y); Dist[y] = Dist[x] + Graph[x][i].second; Chk[y] = chked;
if (far < Dist[y]){
far = Dist[y]; ind = y;
}
}
}
}
return ind;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int i,j,x,y,ans=0,now,end;
for (i=0;i<M;i++){
x = A[i]; y = B[i];
Graph[x].push_back(make_pair(y,T[i]));
Graph[y].push_back(make_pair(x,T[i]));
}
for (i=0;i<N;i++) if (Chk[i] == 0){
y = FindEnd(i,1);
x = FindEnd(y,2);
now = end = Dist[x];
if (ans < end) ans = end;
while (Dist[x] > 0){
for (j=0;j<Graph[x].size();j++){
y = Graph[x][j].first;
if (Dist[x] == Dist[y] + Graph[x][j].second){
x = y; break;
}
}
now = min(now,max(Dist[x],end-Dist[x]));
}
Radius.push_back(now);
}
sort(Radius.rbegin(),Radius.rend());
if (Radius.size() == 2) ans = max(ans,Radius[0]+Radius[1]+L);
else if (Radius.size() > 2){
int last = max(Radius[0]+Radius[1],Radius[1]+Radius[2]+L);
last = min(max(Radius[1]+Radius[0],Radius[0]+Radius[2]+L),last);
last = min(max(Radius[2]+Radius[0],Radius[0]+Radius[1]+L),last);
ans = max(ans,last+L);
}
return ans;
}
