#include "dreaming.h"
#include <bits/stdc++.h>
#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));
using namespace std;
const int N = 1e5 + 5;
const int inf = 1e18;
int visited[N];
vector <pii> adj[N];
vector <int> root;
int down[N], up[N], mxdis;
pii mx1[N], mx2[N];
vector <int> cur;
void dfs1(int u, int p){
cur.emb(u);
visited[u] = true;
for (auto [w, v] : adj[u]) {
if (v == p) continue;
dfs1(v, u);
int dist = w + down[v];
if (dist >= mx1[u].first) mx2[u] = mx1[u], mx1[u] = {dist, v};
else if (dist >= mx2[u].first) mx2[u] = {dist, v};
}
down[u] = mx1[u].first;
}
void dfs2(int u, int p){
for (auto [w, v] : adj[u]) {
if (v == p) continue;
if (v == mx1[u].second) up[v] = w + max(up[u], mx2[u].first);
else up[v] = w + max(up[u], mx1[u].first);
dfs2(v, u);
}
}
int findroot(int u){
cur.clear();
dfs1(u, u);
dfs2(u, u);
pii mn = {inf, inf};
for (auto e : cur) {
int curr = max(down[e], up[e]);
mn = min(mn, {curr, e});
mxdis = max(mxdis, curr);
}
return mn.first;
}
int32_t travelTime(int32_t n, int32_t m, int32_t l, int32_t u[], int32_t v[], int32_t w[]) {
for (int i = 0; i < m; i++) adj[u[i]].emb(w[i], v[i]), adj[v[i]].emb(w[i], u[i]);
for (int i = 0; i < n; i++) if (!visited[i]) root.emb(findroot(i));
int ans = mxdis;
ans = max(ans, root[0] + root[1] + l);
return ans;
}
