#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
using ll = long long;
// #define int ll
const int N = 1e5;
#define fs first
#define sc second
#define mp make_pair
vector<pair<int, int>> g[N];
int vis[N], mxd[N], mx[N];
multiset<int> ms[N];
void dfs(int x, int p) {
vis[x] = 1;
for (auto [u, w]: g[x]) {
if (u != p) {
dfs(u, x);
mxd[x] = max(mxd[x], mxd[u] + w);
}
}
}
void dfs2(int x, int p, int f) {
ms[x].insert(f);
for (auto [u, w]: g[x]) {
if (u != p) {
ms[x].insert(mxd[u] + w);
}
}
mx[x] = *(ms[x].rbegin());
for (auto [u, w]: g[x]) {
if (u != p) {
ms[x].erase(ms[x].lower_bound(mxd[u] + w));
dfs2(u, x, *(ms[x].rbegin()) + w);
ms[x].insert(mxd[u] + w);
}
}
}
int dfs3(int x, int p) {
int res = mx[x];
for (auto [u, w]: g[x]) {
if (u == p) continue;
res = min(res, dfs3(u, x));
}
return res;
}
int travelTime(int n, int m, int l, int u[], int v[], int t[]){
for (int i = 0; i < n; ++i) {
vis[i] = 0;
mxd[i] = 0;
mx[i] = 0;
}
for (int i = 0; i < m; ++i) {
g[u[i]].push_back(mp(v[i], t[i]));
g[v[i]].push_back(mp(u[i], t[i]));
}
int ok = 1;
vector<int> mxdist;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i, -1);
dfs2(i, -1, 0);
mxdist.push_back(dfs3(i, -1));
}
ok &= (int) g[i].size() <= 1;
}
sort(mxdist.begin(), mxdist.end());
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, mx[i]);
}
int sz = (int) mxdist.size();
assert(sz > 0);
if (sz == 1) {
assert(m + 1 == n);
} else {
ans = max(ans, mxdist[sz - 1] + mxdist[sz - 2] + l);
for (int i = 0; i < sz - 2; ++i) {
ans = max(ans, mxdist[sz - 1] + mxdist[i] + l + l);
}
}
// for (int i = 0; i < n; ++i) {
// cout << "! " << i << ' ' << mx[i] << '\n';
// }
return ans;
}
// int32_t main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int nn = 4, M = 2, L = 2;
// int A[]{1, 0};//{0,8,2,5,5,1,1,10};
// int B[]{2, 4};//{8,2,7,11,1,3,9,6};
// int C[]{1000, 2000};//{4,2,4,3,7,1,5,3};
// cout << "answer: " << travelTime(nn, M, L, A, B, C);
// return 0;
// }
