#include "dreaming.h"
#include <vector>
#include <unordered_map>
#include <deque>
#include <iostream>
#include <set>
using namespace std;
const int maxn = 1e5;
const int inf = 2e9;
bool used[maxn];
int cnt = 0;
unordered_map<int, int> dst(int v, vector<vector<pair<int, int>>> &g) {
unordered_map<int, int> d;
deque<int> q;
q.push_back(v);
d[v] = 0;
while (!q.empty()) {
int v = q.front();
q.pop_front();
for (auto [u, w] : g[v]) {
if (!d.count(u)) {
d[u] = d[v] + w;
q.push_back(u);
}
}
}
return d;
}
pair<int, int> goFar(int v, vector<vector<pair<int, int>>> &g) {
auto d1 = dst(v, g);
int best = v;
for (auto [u, x] : d1) {
if (d1[best] < x) {
best = u;
}
++cnt;
used[u] = true;
}
return { best, d1[best] };
}
pair<int, int> findDiam(int v, vector<vector<pair<int, int>>> &g) {
int leafe = goFar(v, g).first;
int best = goFar(leafe, g).first;
int best1 = goFar(best, g).first;
return { best, best1 };
}
int findDiamLen(int v, vector<vector<pair<int, int>>> &g) {
int leafe = goFar(v, g).first;
int best = goFar(leafe, g).first;
return goFar(best, g).second;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
g[u].push_back({ v, T[i] });
g[v].push_back({ u, T[i] });
}
vector<pair<int, int>> dims;
multiset<pair<int, int>> s;
for (int i = 0; i < N; ++i) {
if (!used[i]) {
cnt = 0;
auto [u, v] = findDiam(i, g);
auto d1 = dst(u, g);
auto d2 = dst(v, g);
int vs = -1;
int b1 = inf;
for (auto [u, l] : d1) {
if (b1 > max(l, d2[u])) {
b1 = max(l, d2[u]);
vs = u;
}
}
s.insert({ b1, vs });
}
}
for (int i = 1; i < s.size(); ++i) {
auto [l1, u1] = *s.begin();
s.erase(s.begin());
auto [l2, u2] = *s.begin();
s.erase(s.begin());
g[u1].push_back({ u2, L });
g[u2].push_back({ u1, L });
if (l1 < l2) {
swap(l1, l2);
swap(u1, u2);
}
auto [u, v] = findDiam(u1, g);
auto d1 = dst(u, g);
auto d2 = dst(v, g);
int vs = -1;
int b1 = inf;
for (auto [u, l] : d1) {
if (b1 > max(l, d2[u])) {
b1 = max(l, d2[u]);
vs = u;
}
}
s.insert({ b1, vs });
}
return findDiamLen(0, g);
}
