// #include "dreaming.h"
// int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
// return 0;
// }
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int n = 100000;
int par[n], dep[n], ans[n];
vector<pair<int, int>> adj[n];
int fp(int x) {
if (par[x] == -1) return x;
return par[x] = fp(par[x]);
}
int dfs1(int x, int p) {
int mx = 0;
for (auto &[u, w] : adj[x]) {
if (u == p) continue;
mx = max(mx, w + dfs1(u, x));
}
return dep[x] = mx;
}
void dfs2(int x, int p, int v) {
int t = v;
for (auto &[u, w] : adj[x]) {
if (u == p) continue;
ans[u] = max(ans[u], max(dep[u], v + w));
dfs2(u, x, v + w);
v = max(v, dep[u] + w);
}
v = t;
for (int i = adj[x].size() - 1; i >= 0; i--) {
auto &[u, w] = adj[x][i];
if (u == p) continue;
ans[u] = max(ans[u], max(dep[u], v + w));
dfs2(u, x, v + w);
v = max(v, dep[u] + w);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(par, -1, sizeof(par));
vector<bool> rt(N, false);
vector<int> mn(N, INT_MAX), l;
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
int pa = fp(A[i]), pb = fp(B[i]);
par[pa] = pb;
}
for (int i = 0; i < N; i++) rt[fp(i)] = true;
for (int i = 0; i < N; i++) {
if (!rt[i]) continue;
dfs1(i, -1);
ans[i] = dep[i];
dfs2(i, -1, 0);
}
for (int i = 0; i < N; i++) mn[fp(i)] = min(mn[fp(i)], ans[i]);
for (int i = 0; i < N; i++) {
if (!rt[i]) continue;
l.emplace_back(mn[i]);
}
sort(l.rbegin(), l.rend());
int mx = 0;
if (l.size() >= 2) mx = max(mx, l[0] + l[1] + L);
if (l.size() >= 3) mx = max(mx, l[1] + l[2] + 2 * L);
return mx;
}
