#include <bits/stdc++.h>
#include "dreaming.h"
#if __has_include("debugging.hpp")
#include "debugging.hpp"
#endif
using namespace std;
class Tree {
private:
vector<vector<pair<int, int>>> neighbors;
vector<pair<int, int>> farthest;
vector<pair<int, int>> second_farthest;
vector<int> curr_comp;
void fill_farthest_inside(int at, int prev) {
curr_comp.push_back(at);
vector<pair<int, int>> dists;
for (const auto& [n, dist] : neighbors[at]) {
if (n != prev) {
fill_farthest_inside(n, at);
dists.push_back({farthest[n].first + dist, n});
}
}
std::sort(dists.begin(), dists.end(), std::greater<pair<int, int>>());
farthest[at] = dists.size() >= 1 ? dists[0] : pair<int, int>{0, -1};
second_farthest[at] = dists.size() >= 2 ? dists[1] : pair<int, int>{0, -1};
}
void fill_farthest(int at, int prev, int dist) {
if (dist != -1) {
pair<int, int> prev_path =
(farthest[prev].second != at ? farthest : second_farthest)[prev];
if (farthest[at].first < prev_path.first + dist) {
farthest[at] = {prev_path.first + dist, prev};
} else if (second_farthest[at].first < prev_path.first + dist) {
second_farthest[at] = {prev_path.first + dist, prev};
}
}
for (const auto& [n, dist] : neighbors[at]) {
if (n != prev) { fill_farthest(n, at, dist); }
}
}
public:
vector<vector<int>> comps; // cba to pound out getters or whatever
Tree(const vector<vector<pair<int, int>>>& neighbors)
: neighbors(neighbors),
farthest(neighbors.size(), {-1, -1}),
second_farthest(neighbors.size()) {
for (int i = 0; i < neighbors.size(); i++) {
if (farthest[i] == make_pair(-1, -1)) {
curr_comp = {};
fill_farthest_inside(i, i);
fill_farthest(i, i, -1);
comps.push_back(curr_comp);
}
}
}
int longest_path(int n) { return farthest[n].first; }
};
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; i++) {
adj[a[i]].push_back({b[i], t[i]});
adj[b[i]].push_back({a[i], t[i]});
}
Tree tree(adj);
vector<int> worst;
int baseline = INT32_MIN;
for (const vector<int>& c : tree.comps) {
int farthest = INT32_MAX;
for (int i : c) { farthest = min(farthest, tree.longest_path(i)); }
worst.push_back(farthest);
baseline = max(baseline, farthest);
}
sort(worst.begin(), worst.end());
int w = worst.size();
if (w == 1) {
return baseline;
} else if (w == 2) {
return worst[0] + l + worst[1];
}
int to_hub = worst[w - 2] + l + worst[w - 1];
int otherwise = worst[w - 3] + 2 * l + worst[w - 2];
return max(to_hub, max(otherwise, baseline));
}
