#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(int i=0; i<(int)graph[curr].size(); i++)
{
int y=graph[curr][i].first;
if(vis[y]!=status)
{
q.push(y);
dist[y]=dist[curr]+graph[curr][i].second;
vis[y]=status;
if(max_dist<dist[y])
{
max_dist=dist[y];
index=y;
}
}
}
}
return index;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int ans=0,tmp,End;
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
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<End)
{
ans=End;
}
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;
}
