#include "dreaming.h"
#include <vector>
#include <unordered_map>
#include <deque>
#include <iostream>
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<pair<int, int>, int>> dims;
for (int i = 0; i < N; ++i) {
if (!used[i]) {
cnt = 0;
dims.push_back({ findDiam(i, g), cnt });
}
}
pair<int, int> curr = dims[0].first;
/*cout << "OUT" << endl;
for (auto [x, y] : dims) {
cout << x << ' ' << y << endl;
}*/
for (int i = 1; i < dims.size(); ++i) {
auto d1 = dst(curr.first, g);
auto d2 = dst(curr.second, g);
auto d3 = dst(dims[i].first.first, g);
auto d4 = dst(dims[i].first.second, g);
pair<int, int> cand;
int b1 = inf;
for (auto [u, l] : d1) {
if (b1 > max(l, d2[u])) {
b1 = max(l, d2[u]);
cand.first = u;
}
}
b1 = inf;
for (auto [u, l] : d3) {
if (b1 > max(l, d4[u])) {
b1 = max(l, d4[u]);
cand.second = u;
}
}
//cout << "UNITE " << cand.first << ' ' << cand.second << endl;
g[cand.first].push_back({ cand.second, L });
g[cand.second].push_back({ cand.first, L });
curr = findDiam(cand.first, g);
}
return findDiamLen(0, g);
}
