#include "dreaming.h"
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
int maxt[10100];
int vis[10100];
vector<pair<int,int>>l[10100];
int dfs(int n)
{
if(vis[n])
return 0;
vis[n]=1;
int i;
for(i=0;i<l[n].size();i++)
{
if(!vis[l[n][i].first])
maxt[n]=max(maxt[n],dfs(l[n][i].first)+l[n][i].second);
}
return maxt[n];
}
pair<int,int> dfs2(int n,int t)
{
int i;
if(vis[n])
return {1<<30,1<<30};
vis[n]=1;
pair<int,int>an={0,0};
vector<int>r;
pair<int,int>mal={0,0};
for(i=0;i<l[n].size();i++)
{
if(vis[l[n][i].first])
continue;
r.push_back(-maxt[l[n][i].first]-l[n][i].second);
mal=max(mal,{maxt[l[n][i].first]+l[n][i].second,i});
}
sort(r.begin(),r.end());
for(i=0;i<min(2,(int)r.size());i++)
{
an.first-=r[i];
if(i==0)
an.second-=r[i];
}
an.second=max(an.second,t);
for(i=0;i<l[n].size();i++)
{
if(vis[l[n][i].first])
continue;
int cu=mal.first;
if(mal.second==i)
{
cu=(r.size()>1)?(-r[1]):0;
}
auto a=dfs2(l[n][i].first,max(t+l[n][i].second,cu+l[n][i].second));
an.first=max(an.first,a.first);
an.second=min(an.second,a.second);
}
return an;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int i;
for(i=0;i<M;i++)
{
l[A[i]].push_back({B[i],T[i]});
l[B[i]].push_back({A[i],T[i]});
}
for(i=0;i<N;i++)
{
dfs(i);
}
memset(vis,0,sizeof(vis));
int di=0;
vector<int>rr;
for(i=0;i<N;i++)
{
if(vis[i])
continue;
auto r=dfs2(i,0);
rr.push_back(-r.second);
di=max(di,r.first);
}
int cr=di;
sort(rr.begin(),rr.end());
if(rr.size()>1)
cr=max(cr,-rr[0]-rr[1]+L);
if(rr.size()>2)
cr=max(cr,-rr[1]-rr[2]+L*2);
return cr;
}
