//#ifndef DREAMING_H_INCLUDED
//#define DREAMING_H_INCLUDED
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 1e5 + 5;
vector <point> E[MAXN];
vector <int> component[MAXN];
int boja[MAXN], dist[MAXN], dep[MAXN];
point par[MAXN], mx[MAXN];
void color(int x, int Time){
boja[x] = Time;
component[Time].pb(x);
for(auto e : E[x]){
if(boja[e.first] != -1) continue;
color(e.first, Time);
}
}
point find_furthest(int cmp, int x){
for(auto it : component[cmp])
dist[it] = 0;
queue<int> Q;
Q.push(x);
point ret = point(0, 0);
while(!Q.empty()){
int nx = Q.front(); Q.pop();
for(auto e : E[nx]){
if(dist[e.first] || e.first == x)
continue;
par[e.first] = point(nx, e.second);
dep[e.first] = dep[nx] + 1;
dist[e.first] = dist[nx] + e.second;
ret = max(ret, point(dist[e.first], e.first));
Q.push(e.first);
}
}
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
REP(i, M){
E[ A[i] ].pb( point( B[i], T[i] ) );
E[ B[i] ].pb( point( A[i], T[i] ) );
}
memset(boja, -1, sizeof(boja));
int Time = 0;
REP(i, N)
if(boja[i] == -1)
color(i, Time ++);
int ret = 0;
REP(i, Time){
int a = find_furthest(i, component[i][0]).second;
point najdalji = find_furthest(i, a);
int b = najdalji.second, d = najdalji.first;
if(dep[a] < dep[b])
swap(a, b);
ret = max(ret, d);
mx[i] = point(d, a);
deque<point> lt, rt;
while(dep[a] != dep[b]){
lt.push_back(par[a]);
a = par[a].first;
}
while(a != b){
lt.push_back(par[a]);
a = par[a].first;
rt.push_front(point(b, par[b].second));
b = par[b].first;
}
int sum = 0;
for(auto it : lt){
sum += it.second;
mx[i] = min(mx[i], point(max(d - sum, sum), it.first));
}
for(auto it : rt){
sum += it.second;
mx[i] = min(mx[i], point(max(d - sum, sum), it.first));
}
mx[i] = max(mx[i], find_furthest(i, mx[i].second));
}
sort(mx, mx + Time, greater<point>());
//TRACE(mx[0].first); TRACE(mx[1].first); TRACE(L);
if(Time == 1)
return ret;
else if(Time == 2)
return max(ret, mx[0].first + mx[1].first + L);
else
return max(mx[1].first + mx[2].first + 2 * L, max(ret, mx[0].first + mx[1].first + L));
}
//#endif // DREAMING_H_INCLUDED
