#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];
pair<int, int> dfs2(int v, int p) {
us[v] = true;
multiset<int> q;
q.insert(dp[v]);
for (pair<int, int> u : g[v]) {
if (u.first == p) continue;
q.insert(d[u.first] + u.second);
}
int mx, mn;
mx = mn = *(--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;
pair<int, int> ret = dfs2(u.first, v);
mn = min(ret.first, mn);
mx = max(ret.second, mx);
}
return { mn, mx };
}
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;
}
int ans = 0;
vector<int> w;
for (int i = 0; i < N; ++i) {
if (!us[i]) {
dfs1(i, i);
dp[i] = 0;
pair<int, int> ret = dfs2(i, i);
w.push_back(ret.first);
ans = max(ans, ret.second);
}
}
sort(w.begin(), w.end());
reverse(w.begin(), w.end());
if (w.size() >= 2) {
ans = max(w[0] + w[1] + L, ans);
}
if (w.size() >= 3) {
ans = max(ans, w[1] + w[2] + L + L);
}
return ans;
}
