#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
const int UNVISITED = -1;
const int N = 111111;
int finish;
int d[N];
vector<pair<int, int>> g[N];
vector<int> cc, path;
void dfs(int x, int y) {
cc.push_back(x);
for (auto [a, b] : g[x]) {
if (a == y) continue;
d[a] = d[x] + b;
dfs(a, x);
}
}
void dff(int x, int y) {
if (!path.empty() && path.back() == finish) return;
path.push_back(x);
// cout << x << endl;
if (path.back() == finish) return;
for (auto [a, b] : g[x]) {
if (a == y) continue;
dff(a, x);
if (path.back() == finish) return;
}
path.pop_back();
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
memset(d, UNVISITED, sizeof(d));
for (int i = 0; i < m; i++) {
g[a[i]].push_back({b[i], t[i]});
g[b[i]].push_back({a[i], t[i]});
}
vector<int> r, di;
for (int i = 0; i < n; i++) {
if (d[i] == UNVISITED) {
cc.clear();
d[i] = 0;
dfs(i, N);
int nu = i;
for (int x : cc) {
if (d[x] > d[nu]) nu = x;
}
cc.clear();
d[nu] = 0;
dfs(nu, N);
int ku = nu;
for (int x : cc) {
if (d[x] > d[ku]) ku = x;
}
path.clear();
finish = ku;
dff(nu, N);
int diam = d[ku];
int centre = 0;
for (int j = 0; j < (int)path.size(); j++) {
if (abs(2 * d[path[j]] - diam)
<= abs(2 * d[path[centre]] - diam)) {
centre = j;
}
}
centre = path[centre];
int radius = max(d[centre], diam - d[centre]);
r.push_back(radius);
di.push_back(diam);
/*
cerr << nu << " " << ku << " " << diam << endl;
cerr << centre << " " << radius << endl;
cerr << "=================\n";
for (int i : path)
cerr << i << " ";
cerr << "\n=================\n";
*/
}
}
sort(r.rbegin(), r.rend());
if (all_of(r.begin(), r.end(), [](int i) { return i == 0; })) {
return 2 * l;
}
if (r.size() == 1) return di[0];
return max(*max_element(di.begin(), di.end()), r[0] + r[1] + l);
}
