#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAX=1e5+10;
const int INF=(1<<30);
vector<pair<int,int> > graph[MAX];
vector<int> radius;
int dist[MAX];
int vis[MAX];
int FindEnd(int start, int status)
{
queue<int> q;
int index,max_dist;
index=start;max_dist=0;
q.push(start);
vis[start]=status;
dist[start]=0;
while(!q.empty())
{
int curr=q.front();
q.pop();
for(auto neighbour:graph[curr])
{
int newidx=neighbour.first;
int cost=neighbour.second;
if(vis[newidx]!=status)
{
vis[newidx]=status;
q.push(newidx);
dist[newidx]=dist[curr]+cost;
if(max_dist<dist[newidx])
{
max_dist=dist[newidx];
index=newidx;
}
}
}
}
return index;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int ans=0,tmp,end;
for(int i=0; i<M; i++)
{
int a=A[i];
int b=B[i];
int cena=T[i];
graph[a].push_back({b,cena});
graph[b].push_back({a,cena});
}
for(int i=0; i<N; i++)
{
if(vis[i]==0)
{
int y=FindEnd(i,1);
int x=FindEnd(y,2);
tmp=end=dist[x];
if(ans<tmp)
{
ans=tmp;
}
while(dist[x]>0)
{
for(int j=0; j<(int)graph[x].size(); j++)
{
y=graph[x][j].first;
if(dist[x]==dist[y]+graph[x][j].second)
{
x=y;
break;
}
}
tmp=min(tmp,max(dist[x],end-dist[x]));
}
radius.push_back(tmp);
}
}
sort(radius.begin(),radius.end());
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;
}
