#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> sr[100001];
void ff(vector<pair<int, int>> ap[], int cur, int par, int g)
{
sr[g].push_back(cur);
for (auto& [p, w] : ap[cur]) {
if (p == par) continue;
ff(ap, p, cur, g);
}
}
vector<int> mn(100005, -1);
vector<int> dij(vector<pair<int, int>> ap[], int n, int s, int g) {
for (auto& p : sr[g]) mn[p] = 2e9;
mn[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({mn[s], s});
while (pq.size()) {
auto [w, u] = pq.top();
pq.pop();
if (mn[u] < w) continue;
for (auto& [v, d] : ap[u]) {
if (mn[v] > w + d) {
mn[v] = w + d;
pq.push({mn[v], v});
}
}
}
//for (auto& p : sr[g]) cout << mn[p] << ' ';
//cout << '\n';
return mn;
}
int findc(vector<pair<int, int>> ap[], int n, int s, int g)
{
vector<int> sm = dij(ap, n, s, g);
int l = s;
for (auto& p : sr[g]) {
//cout << mn[p] << ' ';
if (mn[p] > mn[l]) l = p;
}
//cout << mn[l] << ' ';
vector<int> lm = dij(ap, n, l, g);
int r = l;
for (auto& p : sr[g]) {
if (mn[p] > mn[r]) r = p;
}
vector<int> rm = dij(ap, n, r, g);
int md = 2e9;
for (auto& p : sr[g]) {
md = min(md, max(lm[p], rm[p]));
}
return md;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
vector<pair<int, int>> ap[n + 1];
for (int i = 0; i < m; i++) {
ap[A[i]].push_back({B[i], T[i]});
ap[B[i]].push_back({A[i], T[i]});
}
int g = 0;
int f1, f2, f3;
vector<int> arr;
for (int i = 0; i < n; i++) {
if (mn[i] == -1) {
ff(ap, i, -1, ++g);
int val = findc(ap, n, i, g);
arr.push_back(val);
}
}
sort(arr.rbegin(), arr.rend());
//for (auto& p : arr) cout << p << ' ';
//cout << '\n';
int ans;
if (arr.size() <= 2) ans = arr[0] + arr[1] + l;
else ans = max(arr[0] + arr[1] + l, l * 2 + arr[1] + arr[2]);
return ans;
}
