#include <bits/stdc++.h>
#include "dreaming.h"
std::vector <std::vector <std::pair <int, int>>> g;
std::vector <std::pair <int, int>> d1, d2;
std::vector <int> d;
std::vector <bool> vis;
void dfs1(int node, int par) {
vis[node] = true;
for (auto p : g[node]) if (p.first != par) {
int x = p.first, w = p.second;
dfs1(x, node);
d2[node] = std::max(d2[node], { d1[x].first + w, x });
if (d2[node] > d1[node]) std::swap(d1[node], d2[node]);
}
}
std::vector <int> nows;
void dfs2(int node, int par, int dist) {
vis[node] = true;
nows.push_back(node);
d[node] = std::max(d1[node].first, dist);
for (auto p : g[node]) if (p.first != par) {
int x = p.first, w = p.second;
if (x == d1[node].second) dfs2(x, node, std::max(d2[node].first, dist) + w);
else dfs2(x, node, d[node] + w);
}
}
bool comp(const int& a, const int& b) {
return d[a] < d[b];
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
g.resize(n);
d1.resize(n);
d2.resize(n);
d.resize(n);
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] });
}
vis.resize(n, false);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs1(i, -1);
}
}
vis.clear();
vis.resize(n, false);
std::vector <int> ws;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs2(i, -1, 0);
std::sort(nows.begin(), nows.end(), comp);
ws.push_back(d[nows[0]]);
nows.clear();
}
}
std::sort(ws.rbegin(), ws.rend());
int maxdia = 0;
for (int x : d) maxdia = std::max(maxdia, x);
if (ws.size() == size_t(1)) return maxdia;
if (ws.size() == size_t(2)) return std::max(maxdia, ws[0] + ws[1] + l);
return std::max({ ws[0] + ws[1] + l, ws[1] + ws[2] + l + l, maxdia });
}
