#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "dreaming.h"
using namespace std;
const int N_MAX = 1e5 + 8;
vector<pair<int, int>> g[N_MAX];
int d[N_MAX], dp[N_MAX];
void dfs1(int v, int p) {
d[v] = 0;
for (pair<int, int> u : g[v]) {
if (u.first == p) continue;
dfs1(u.first, v);
d[v] = max(d[v], d[u.first] + u.second);
}
}
bool us[N_MAX];
int dfs2(int v, int p) {
us[v] = true;
multiset<int> q;
if (p != -1) {
q.insert(dp[v]);
}
for (pair<int, int> u : g[v]) {
if (u.first == p) continue;
q.insert(d[u.first] + u.second);
}
int ret = *(--q.end());
for (pair<int, int> u : g[v]) {
if (u.first == p) continue;
q.erase(q.find(d[u.first] + u.second));
dp[u.first] = *(--q.end()) + u.second;
q.insert(d[u.first] + u.second);
}
q.clear();
for (pair<int, int> u : g[v]) {
if (u.first == p) continue;
ret = min(dfs2(u.first, v), ret);
}
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; ++i) {
g[A[i]].emplace_back(B[i], T[i]);
g[B[i]].emplace_back(A[i], T[i]);
}
for (int i = 0; i < N; ++i) {
us[i] = false;
}
vector<int> w;
for (int i = 0; i < N; ++i) {
if (!us[i]) {
dfs1(i, i);
dp[i] = 0;
w.push_back(dfs2(i, i));
}
}
sort(w.begin(), w.end());
reverse(w.begin(), w.end());
if (w.size() == 2) {
return w[0] + w[1] + L;
}
else {
return max(w[0] + w[1] + L, w[1] + w[2] + L + L);
}
}
