/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: dreaming
* score: 100.0
* date: 2019-06-27 09:30:59.412917
*/
#include "dreaming.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < pii > vp;
const int N = 1e5 + 500;
const int INF = 0x3f3f3f3f;
int d[N], u[N], dp[N], min_sol;
vp v[N];
void calc_d(int x,int lst){
for(pii y : v[x]){
if(y.X == lst) continue;
calc_d(y.X, x);
d[x] = max(d[y.X] + y.Y, d[x]);
}
}
void calc(int x,int lst){
int dos = u[x];
for(pii y : v[x]){
if(y.X == lst) continue;
u[y.X] = max(u[y.X],y.Y + dos);
dos = max(dos, d[y.X] + y.Y);
}
reverse(v[x].begin(), v[x].end());
dos = 0;
for(pii y : v[x]){
if(y.X == lst) continue;
u[y.X] = max(u[y.X],y.Y + dos);
dos = max(dos, d[y.X] + y.Y);
}
reverse(v[x].begin(), v[x].end());
dp[x] = min(max(u[x], d[x]), dp[x]);
min_sol = max(min_sol, d[x] + u[x]);
for(pii y : v[x]){
if(y.X == lst) continue;
calc(y.X, x);
dp[x] = min(dp[x], dp[y.X]);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0;i < M;i++){
v[A[i]].PB({B[i], T[i]});
v[B[i]].PB({A[i], T[i]});
}
memset(dp, INF, sizeof(dp));
vi f;
for(int i = 0;i < N;i++){
if(dp[i] != INF) continue;
calc_d(i, i); calc(i, i);
f.PB(dp[i]);
}
sort(f.rbegin(), f.rend());
if(f.size() == 1) return max(f[0], min_sol);
else if(f.size() == 2) return max(f[0] + f[1] + L, min_sol);
return max(max(f[0] + f[1] + L, f[1] + f[2] + 2 * L), min_sol);
}
