#include "dreaming.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
template <typename T>
inline bool ckmin(T& x, const T& y) {
return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool ckmax(T& x, const T& y) {
return x < y ? x = y, 1 : 0;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
dbg(N, M, L);
auto merge = [&](int a, int b, int w) {
int left = std::max(a, w + b);
int right = std::max(b, w + a);
return std::min(left, right);
};
std::vector<std::vector<std::pair<int, int>>> adj(N);
for (int i = 0; i < M; i++) {
dbg(A[i], B[i], T[i]);
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
std::priority_queue<int> pq;
std::vector<int> vis(N), comp;
std::vector<int> dp(N);
std::vector<int> up(N);
auto dfs1 = [&](auto self, int u, int p) -> void {
comp.push_back(u);
vis[u] = 1;
dp[u] = 0;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
self(self, v, u);
ckmax(dp[u], dp[v] + w);
}
};
int max_val = 0;
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
auto dfs2 = [&](auto self, int u, int p) -> int {
int lmao = std::max(up[u], dp[u]);
ckmax(max_val, lmao);
std::pair<int, int> good = {0, 0};
for (auto [v, w] : adj[u]) {
if (v == p) continue;
if (w + dp[v] > good.first) {
good.second = good.first;
good.first = w + dp[v];
} else if (w + dp[v] > good.second) {
good.second = w + dp[v];
}
}
for (auto [v, w] : adj[u]) {
if (v == p) continue;
up[v] = w + std::max(up[u], good.first == w + dp[v] ? good.second
: good.first);
ckmin(lmao, self(self, v, u));
}
return lmao;
};
dfs1(dfs1, i, i);
pq.push(dfs2(dfs2, i, i));
}
dbg(max_val);
dbg(pq);
dbg(pq.size());
while (pq.size() > 1) {
auto best1 = pq.top();
pq.pop();
auto best2 = pq.top();
pq.pop();
dbg(best1, best2);
ckmax(max_val, best1 + best2 + L);
pq.push(merge(best1, best2, L));
}
return max_val;
}
