#ifndef __APPLE__
#include "dreaming.h"
#endif
#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
Vec<Vec<std::pair<int, int>>> graph(N);
for (int i = 0; i < M; ++i) {
graph[A[i]].emplace_back(B[i], T[i]);
graph[B[i]].emplace_back(A[i], T[i]);
}
Vec<bool> done(N);
Vec<Vec<int>> max(N);
for (int i = 0; i < N; ++i) {
max[i].resize(graph[i].size());
}
auto dfs = [&](auto dfs, const int u) -> int {
done[u] = true;
int ret = 0;
for (int i = 0; i < (int) graph[u].size(); ++i) {
const auto [v, c] = graph[u][i];
if (!done[v]) {
max[u][i] = dfs(dfs, v) + c;
ret = std::max(ret, max[u][i]);
}
}
return ret;
};
int ans = 0;
auto apply = [&](auto apply, const int u, const int p, const int up) -> int {
for (int i = 0; i < (int) graph[u].size(); ++i) {
const auto [v, c] = graph[u][i];
if (v == p) {
max[u][i] = up + c;
}
}
Vec<int> pref(max[u].size() + 1);
Vec<int> suff(max[u].size() + 1);
for (int i = 0; i < (int) max[u].size(); ++i) {
pref[i + 1] = std::max(pref[i], max[u][i]);
suff[i + 1] = std::max(suff[i], max[u][max[u].size() - i - 1]);
}
int ret = pref[max[u].size()];
ans = std::max(ans, ret);
for (int i = 0; i < (int) graph[u].size(); ++i) {
ans = std::max(ans, pref[i] + suff[max[u].size() - i]);
const auto [v, c] = graph[u][i];
if (v != p) {
ret = std::min(ret, apply(apply, v, u, std::max(pref[i], suff[max[u].size() - i - 1])));
}
}
return ret;
};
Vec<int> roots;
for (int i = 0; i < N; ++i) {
if (!done[i]) {
dfs(dfs, i);
roots.push_back(apply(apply, i, i, 0));
}
}
std::sort(roots.begin(), roots.end());
const auto center = roots.back();
roots.pop_back();
if (roots.empty()) {
return center;
}
ans = std::max(ans, center + L + roots.back());
Vec<int> pref(roots.size() + 1);
Vec<int> suff(roots.size() + 1);
for (int i = 0; i < (int) roots.size(); ++i) {
pref[i + 1] = std::max(pref[i], roots[i]);
suff[i + 1] = std::max(suff[i], roots[roots.size() - i - 1]);
}
for (int i = 0; i <= (int) roots.size(); ++i) {
ans = std::max(ans, pref[i] + suff[roots.size() - i] + 2 * L);
}
return ans;
}
#ifdef __APPLE__
int A[100];
int B[100];
int T[100];
int main() {
int N, M, L;
std::cin >> N >> M >> L;
for (int i = 0; i < M; ++i) {
std::cin >> A[i] >> B[i] >> T[i];
}
std::cout << travelTime(N, M, L, A, B, T) << '\n';
return 0;
}
#endif
