#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int n, int m, int l, int edge_a[], int edge_b[], int edge_c[]) {
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[edge_a[i]].push_back({edge_b[i], edge_c[i]});
g[edge_b[i]].push_back({edge_a[i], edge_c[i]});
}
vector<int> dep(n, 0), up(n, 0);
vector<bool> vis(n, 0);
int cur_diam, cur_mx_dist;
function<void(int)> dfs1 = [&] (int a) {
vector<pair<int, int>> nw_g;
vis[a] = 1;
for (auto &it : g[a]) {
int b = it.first, c = it.second;
if (!vis[b]) {
nw_g.push_back(it);
dfs1(b);
cur_diam = max(cur_diam, dep[a] + dep[b] + c);
dep[a] = max(dep[a], dep[b] + c);
}
}
g[a] = nw_g;
};
function<void(int)> dfs2 = [&] (int a) {
cur_mx_dist = min(cur_mx_dist, max(up[a], dep[a]));
for (int S = 0; S < 2; S++) {
int R = 0;
for (auto &it : g[a]) {
int b = it.first, c = it.second;
up[b] = max(up[b], up[a] + c);
up[b] = max(up[b], R + c);
R = max(R, dep[b] + c);
}
reverse(g[a].begin(), g[a].end());
}
for (auto &it : g[a]) {
int b = it.first, c = it.second;
dfs2(b);
}
};
vector<int> guys;
int sol = 0;
for (int r = 0; r < n; r++) {
if (!vis[r]) {
cur_diam = 0;
cur_mx_dist = (int) 1e9 + 7;
dfs1(r);
dfs2(r);
guys.push_back(cur_mx_dist);
sol = max(sol, cur_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;
}
