#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 100'000;
#define BUGO(x) cerr << #x << " = " << x << '\n';
struct Jmp {
int to, w;
operator int&() { return to; }
};
vector<Jmp> nei[maxN];
bool used[maxN];
void Maxi(auto& l, auto r) { l = max(l, r); }
int dpu[maxN], dpd[maxN];
void DFSD(int v, int par = -1)
{
used[v] = true;
for (Jmp& to: nei[v])
if (to != par) {
DFSD(to, v);
dpd[v] = max(dpd[v], dpd[to] + to.w);
}
}
int diam = 0, farth = maxN;
void DFSU(int v, int par = -1)
{
if (par == -1) {
diam = 0;
farth = maxN;
}
pair<int, int> mx = {0, 0};
for (Jmp& to: nei[v])
if (to != par) {
Maxi(mx.second, dpd[to] + to.w);
if (mx.second > mx.first) swap(mx.first, mx.second);
}
Maxi(diam, mx.first + mx.second);
farth = min(farth, max(dpd[v], dpu[v]));
for (Jmp& to: nei[v])
if (to != par)
{
Maxi(dpu[to], max(dpu[v], mx.first == dpd[to] + to.w ? mx.second : mx.first) + to.w);
DFSU(to, v);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int w[]) {
for (int i = 0; i < m; ++i) {
nei[a[i]].push_back({b[i], w[i]});
nei[b[i]].push_back({a[i], w[i]});
}
vector<int> far;
int ans = 0;
for (int i = 0; i < n; ++i)
if (!used[i]) {
DFSD(i, -1);
DFSU(i, -1);
far.push_back(farth);
Maxi(ans, diam);
BUGO(i)
BUGO(diam)
BUGO(farth)
}
sort(far.begin(), far.end(), greater<int>());
if (far.size() >= 2)
Maxi(ans, far[0] + l + far[1]);
if (far.size() >= 3)
Maxi(ans, far[1] + l + l + far[2]);
return ans;
}
