//#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], dp_down[MAXN], dp_up[MAXN], sol;
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);
}
}
void dfs_down(int x, int p = -1){
for(auto e : E[x]){
if(e.first == p) continue;
dfs_down(e.first, x);
dp_down[x] = max(dp_down[x], dp_down[e.first] + e.second);
}
}
void merge(point &a, int x){
if(x > a.first){
a.second = a.first;
a.first = x;
}
else if(x > a.second)
a.second = x;
}
void dfs_up(int x, int p = -1){
point maxi = point(0, 0);
for(auto e : E[x]){
if(e.first == p) continue;
merge(maxi, dp_down[e.first] + e.second);
}
for(auto e : E[x]){
if(e.first == p) continue;
if(maxi.first == dp_down[e.first] + e.second)
dp_up[e.first] = maxi.second + e.second;
else
dp_up[e.first] = maxi.first + e.second;
dp_up[e.first] = max(dp_up[e.first], dp_up[x] + e.second);
dfs_up(e.first, x);
}
sol = max(sol, maxi.first + maxi.second);
}
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 ++);
vector<int> v;
REP(i, Time){
dfs_down(component[i][0]);
dfs_up(component[i][0]);
int mn = 1e9;
for(auto it : component[i]){
mn = min(mn, max(dp_down[it], dp_up[it]));
}
v.pb(mn);
}
sort(v.rbegin(), v.rend());
if(Time == 1)
return sol;
else if(Time == 2)
return max(sol, v[0] + v[1] + L);
else
return max(v[1] + v[2] + 2 * L, max(sol, v[0] + v[1] + L));
}
//#endif // DREAMING_H_INCLUDED
