#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int) 1e5 + 7;
const int INF = (int) 2e9;
int dep[N], up[N];
bool vis[N];
vector<pair<int, int>> g[N];
int n, m, l;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
m = M;
l = L;
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]});
}
int diam, mx_dist;
function<void(int)> dfs1 = [&] (int a) {
vector<pair<int, int>> gg;
vis[a] = 1;
for (auto &b : g[a]) {
if (!vis[b.first]) {
gg.push_back(b);
dfs1(b.first);
diam = max(diam, dep[a] + dep[b.first] + b.second);
dep[a] = max(dep[a], dep[b.first] + b.second);
}
}
g[a] = gg;
};
function<void(int)> dfs2 = [&] (int a) {
mx_dist = min(mx_dist, max(up[a], dep[a]));
for (int it = 0; it < 2; it++) {
int r = 0;
for (auto &b : g[a]) {
up[b.first] = max(up[b.first], up[a] + b.second);
up[b.first] = max(up[b.first], r + b.second);
r = max(r, dep[b.first] + b.second);
}
reverse(g[a].begin(), g[a].end());
}
for (auto &b : g[a]) {
dfs2(b.first);
}
};
vector<int> guys;
int sol = 0;
for (int r = 0; r < n; r++) {
if (!vis[r]) {
diam = 0;
mx_dist = INF;
dfs1(r);
dfs2(r);
guys.push_back(mx_dist);
sol = max(sol, diam);
}
}
sort(guys.rbegin(), guys.rend());
if ((int) guys.size() >= 2) {
sol = max(sol, guys[0] + guys[1] + l);
}
if ((int) guys.size() >= 3) {
sol = max(sol, guys[1] + guys[2] + 2 * l);
}
return sol;
}
