#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int posecen[100005];
vector<vector<int>>a(100005);
map<pair<int,int>,int>mapa;
int val[100005];
static void dfs(int k,int &maxd,int &d,int dubina,vector<int>&pom)
{
posecen[k]=true;
if(dubina>maxd)
{
maxd=dubina;
d=k;
}
pom.push_back(k);
for(int i=0;i<a[k].size();i++)
{
if(!posecen[a[k][i]])
{
dfs(a[k][i],maxd,d,dubina+mapa[make_pair(k,a[k][i])],pom);
}
}
}
static void nadjiprecnik(int k,int t,vector<int>&precnik,bool &nadjen)
{
posecen[k]=true;
if(k==t)
{
precnik.push_back(t);
nadjen=true;
return;
}
for(int i=0;i<a[k].size();i++)
{
if(!posecen[a[k][i]])
{
nadjiprecnik(a[k][i],t,precnik,nadjen);
if(nadjen)
{
precnik.push_back(k);
return;
}
}
}
}
int travelTime(int N, int M, int L,int A[], int B[], int T[])
{
for(int i=0;i<N;i++)posecen[i]=false;
for(int i=0;i<M;i++)
{
a[A[i]].push_back(B[i]);
a[B[i]].push_back(A[i]);
mapa[make_pair(A[i],B[i])]=T[i];
mapa[make_pair(B[i],A[i])]=T[i];
}
vector<pair<int,int>>niz;
for(int i=0;i<N;i++)
{
if(!posecen[i])
{
if(a[i].size()==0)
{
niz.push_back(make_pair(0,0));
posecen[i]=true;
continue;
}
int maxd=0;
vector<int>pom;
vector<int>pom1;
int k1=i;
dfs(i,maxd,k1,0,pom);
for(int j=0;j<pom.size();j++)posecen[pom[j]]=false;
maxd=0;
int k2=k1;
dfs(k1,maxd,k2,0,pom1);
for(int j=0;j<pom1.size();j++)posecen[pom1[j]]=false;
vector<int>precnik;
bool nadjen=false;
int r=maxd;
nadjiprecnik(k1,k2,precnik,nadjen);
for(int j=0;j<precnik.size();j++)posecen[precnik[j]]=false;
for(int j=0;j<pom.size();j++)posecen[pom[j]]=true;
int mind=INT_MAX;
int x=0;
int num1=0,num2=0;
for(int j=0;j<(int)precnik.size()-1;j++)
{
pair<int,int> z=make_pair(precnik[j],precnik[j+1]);
x+=mapa[z];
if(abs(x-(r-x))<mind)
{
mind=abs(x-(r-x));
num1=x;
num2=r-x;
}
}
pair<int,int>z=make_pair(max(num1,num2),min(num1,num2));
niz.push_back(z);
}
}
sort(niz.begin(),niz.end());
reverse(niz.begin(),niz.end());
int maxval=niz[0].first+niz[0].second;
if(niz.size()>1)
{
maxval=max(maxval,niz[0].first+L+niz[1].first);
}
if(niz.size()>2)
{
maxval=max(maxval,niz[1].first+2*L+niz[2].first);
}
return maxval;
}
