#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 100005;
int a[NN], b[NN], t[NN];
vector<pair<int, int>> g[NN];
int vis[NN];
int mx[NN], mx2[NN];
int far[NN];
int mn[NN];
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n, m, l;
n = N, m = M, l = L;
for (int i = 0; i < m; ++i) {
a[i] = A[i];
b[i] = B[i];
t[i] = T[i];
}
for (int i = 0; i < m; ++i) {
g[a[i]].emplace_back(b[i], t[i]);
g[b[i]].emplace_back(a[i], t[i]);
}
int ncc = 0;
vector<int> d(n + 1);
int mxd = 0;
function<void(int, int)> Dfs = [&](int v, int p) {
vis[v] = ncc;
for (auto [u, w] : g[v]) {
if (u != p) {
Dfs(u, v);
mx2[v] = max(mx2[v], mx[u] + w);
if (mx2[v] > mx[v]) {
swap(mx2[v], mx[v]);
}
}
}
d[ncc] = max(d[ncc], mx[v] + mx2[v]);
mxd = max(mxd, d[ncc]);
};
for (int i = 1; i <= n + 1; ++i) mn[i] = 2e9;
function<void(int, int, int)> Dfs2 = [&](int v, int p, int up) {
far[v] = max(mx[v], up);
mn[ncc] = min(mn[ncc], far[v]);
for (auto [u, w] : g[v]) {
if (u == p) continue;
int nup = max(up, mx[v] == mx[u] + w ? mx2[v] : mx[v]) + w;
Dfs2(u, v, nup);
}
};
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
ncc++;
Dfs(i, i);
Dfs2(i, i, 0);
}
}
for (int i = ncc + 1; i <= n + 1; ++i) mn[i] = 0;
sort(mn + 1, mn + 1 + ncc, greater<int>());
int ans = max({mxd, l + mn[1] + mn[2], mn[2] + mn[3] + l + l});
return ans;
}
