#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define num long long
#define next first
#define cost second
#define t_road pair<int, num>
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define ndata vector<num>
graph roads;
// here, max is refered as the first maximal
// mix is refered as the second maximal
ndata max_diameter;
ndata mix_diameter;
ndata depth;
ndata visit_id; num stage = 0;
void replace (int node, num nw_d) {
if (nw_d >= max_diameter[node]) {
mix_diameter[node] = max_diameter[node];
max_diameter[node] = nw_d;
} else if (mix_diameter[node] < nw_d)
mix_diameter[node] = nw_d;
}
num get (int node, int nxt, num cst) {
if (max_diameter[node] == max_diameter[nxt] + cst) return mix_diameter[node];
return max_diameter[node];
}
num dfs_diam (int node, int parent, num local_depth) {
max_diameter[node] = 0;
mix_diameter[node] = 0;
visit_id[node] = stage;
depth[node] = local_depth;
for (t_road road : roads[node]) {
if (parent == road.next) continue ;
int nw_d = dfs_diam(road.next, node, local_depth + road.cost) - local_depth;
replace(node, nw_d);
}
return max_diameter[node] + local_depth;
}
void dfs_replace (int node, int parent, num max_depth) {
replace(node, max_depth);
visit_id[node] = stage;
for (t_road road : roads[node]) {
if (parent == road.next) continue ;
dfs_replace(road.next, node, road.cost + get(node, road.next, road.cost));
}
}
num min_component (int node, int parent) {
num val = max_diameter[node];
visit_id[node] = stage;
for (t_road road : roads[node]) {
if (parent == road.next) continue ;
val = min(val, min_component(road.next, node));
}
return val;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
roads.resize(N);
max_diameter.resize(N, -1);
mix_diameter.resize(N, -1);
depth.resize(N, -1);
visit_id.resize(N, -1);
for (int i = 0; i < M; i ++) {
roads[A[i]].push_back({ B[i], T[i] });
roads[B[i]].push_back({ A[i], T[i] });
}
for (int i = 0; i < N; i ++)
if (visit_id[i] != stage)
dfs_diam(i, -1, 0);
stage ++;
for (int i = 0; i < N; i ++)
if (visit_id[i] != stage)
dfs_replace(i, -1, 0);
stage ++;
vector<num> values;
for (int i = 0; i < N; i ++)
if (visit_id[i] != stage)
values.push_back( min_component(i, -1) );
stage ++;
sort(values.rbegin(), values.rend());
//for (int mu : values)
// cout << mu << " ";
//cout << endl;
if (values.size() == 1) return values[0];
if (values.size() == 2) return values[0] + values[1] + L;
return L + values[1] + max(values[0], values[2] + L);
}
