#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 obelezi(int k)
{
posecen[k]=true;
val[k]=0;
for(int i=0;i<a[k].size();i++)
{
if(!posecen[a[k][i]])
{
obelezi(a[k][i]);
val[k]=max(val[k],val[a[k][i]]+mapa[make_pair(k,a[k][i])]);
//cout<<val[k]<<" "<<k<<endl;
}
}
}
static int uredi(int k,int trmin)
{
int maxval=0;
int t=-1;
int drugimax=0;
for(int i=0;i<a[k].size();i++)
{
if(val[a[k][i]]+mapa[make_pair(a[k][i],k)]>maxval)
{
t=a[k][i];
drugimax=maxval;
maxval=val[a[k][i]]+mapa[make_pair(a[k][i],k)];
}
else
drugimax=max(drugimax,val[a[k][i]]+mapa[make_pair(a[k][i],k)]);
}
val[k]=drugimax;
if(a[k].size()==0)return 0;
if(maxval>=trmin)
{
return trmin;
}
return uredi(t,maxval);
}
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<int>niz;
for(int i=0;i<N;i++)
{
if(!posecen[i])
{
obelezi(i);
int pom=uredi(i,INT_MAX);
niz.push_back(pom);
}
}
sort(niz.begin(),niz.end());
int br=0;
vector<int>niz1;
vector<int>niz2;
for(int cnt=0;cnt<niz.size();cnt+=2)niz1.push_back(niz[cnt]);
for(int cnt=1;cnt<niz.size();cnt+=2)niz2.push_back(niz[cnt]);
reverse(niz1.begin(),niz1.end());
reverse(niz2.begin(),niz2.end());
int val1=INT_MIN;
int val2=INT_MIN;
for(int i=0;i<niz1.size();i++)val1=max(val1,niz1[i]+i*L);
for(int i=0;i<niz2.size();i++)val2=max(val2,niz2[i]+i*L);
return val1+val2+L;
}
