#include <cstdio>
#include "dreaming.h"
#include <vector>
#include <algorithm>
#define DIMN 100010
using namespace std;
int f[DIMN] , vc , rc,dist[DIMN] , a[DIMN] , b[DIMN] , c[DIMN],dp[DIMN];
vector <pair <int,int> > v[DIMN];
int arb[DIMN];
int dfs_initial (int nod , int ok){ /// return diametru arbore + calcul distante
int i,vecin , maxi1, maxi2;
f[nod] = 1;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].first;
if (!f[vecin]){
dfs_initial (vecin , 0);
dist[nod] = max (dist[nod] , dist[vecin] + v[nod][i].second);
}
}
if (ok == 1){ /// acum aflam diametrul
if (v[nod].size() == 1){
return dist[nod];
}
maxi1 = maxi2 = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].first;
if (maxi1 < dist[vecin] + v[nod][i].second){
maxi2 = maxi1;
maxi1 = dist[vecin] + v[nod][i].second;
}
else if (maxi2 < dist[vecin] + v[nod][i].second){
maxi2 = dist[vecin] + v[nod][i].second;
}
}
return maxi1 + maxi2; /// diametrul arborelui curent
}
else return 0;
}
void dfs_process (int nod, int tt, int dup){
int i,vecin , maxi1 , maxi2 , pmaxi1;
/// daca il faci pe nod radacina , dmax e fie dist[nod] fie dup
dp[nod] = max (dist[nod] , dup);
vc = min(vc , max(dist[nod] , dup) );
maxi1 = maxi2 = 0;
pmaxi1 = 0;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].first;
if (vecin == tt)
continue;
if (maxi1 < dist[vecin] + v[nod][i].second){
maxi2 = maxi1;
maxi1 = dist[vecin] + v[nod][i].second;
pmaxi1 = vecin;
}
else if (maxi2 < dist[vecin] + v[nod][i].second){
maxi2 = dist[vecin] + v[nod][i].second;
}
}
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i].first;
if (vecin==tt)
continue;
if (vecin == pmaxi1)
dfs_process (vecin , nod , v[nod][i].second + max (dup , maxi2));
else
dfs_process (vecin , nod , v[nod][i].second + max (dup , maxi1));
}
}
int travelTime (int n , int m , int l , int a[] , int b[] , int c[]){
int i , elem , inter , diam_max = 0;
elem = 0;
for (i=1;i<=m;i++){
a[i-1]++;
b[i-1]++;
v[a[i-1]].push_back(make_pair(b[i-1] , c[i-1]));
v[b[i-1]].push_back(make_pair(a[i-1] , c[i-1]));
}
for (i=1;i<=n;i++){
if (!f[i]){
diam_max = max (diam_max , dfs_initial(i,1));
vc = 2000000000;
dfs_process (i, 0 , 0);
/// vc = valoarea arborelui curent
arb[++elem] = vc;
}
}
sort (arb + 1, arb + elem + 1);
int sol = diam_max;
if (elem > 1)
sol = max ( sol , arb[elem] + l + arb[elem-1] );
if (elem > 2)
sol = max ( sol , arb[elem-1] + 2 * l + arb[elem-2] );
return sol;
}
