#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "dreaming.h"
#endif
const int N = 100005;
int dp[N][4];
vector<pair<int, int> > v[N];
vector<int> ve;
bool bo[N];
pair<int, int> ovod(int dg, int op) {
bo[dg] = 1;
pair<int, int> dr = {0, dg};
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
pair<int, int> p = ovod(v[dg][i].first, dg);
int l = v[dg][i].second;
if(p.first + l > dr.first) dr = {p.first + l, p.second};
}
}
return dr;
}
void ovog(int dg, int op, int mn, int sv) {
ve.push_back(mn);
if(dg == sv) {
ve[0] = -1;
return;
}
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
ovog(v[dg][i].first, dg, mn + v[dg][i].second, sv);
if(ve[0] == -1) return;
}
}
ve.pop_back();
}
void ovoq(int dg, int op) {
dp[dg][0] = dg;
dp[dg][1] = dp[dg][2] = dp[dg][3] = 0;
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
ovoq(v[dg][i].first, dg);
int x = dp[v[dg][i].first][1];
int l = v[dg][i].second;
if(x + l > dp[dg][1]) {
dp[dg][2] = dp[dg][1];
dp[dg][1] = x + l;
dp[dg][0] = v[dg][i].first;
} else if(x + l > dp[dg][2]) {
dp[dg][2] = x + l;
}
}
}
}
int ovox(int dg, int op) {
// cout << "[2] " << dg << " " << dp[dg][0] << " " << dp[dg][1] << " " << dp[dg][2] << " " << dp[dg][3] << "\n";
int dr = max(dp[dg][1], dp[dg][3]);
for(int i = 0; i < v[dg].size(); ++i) {
if(v[dg][i].first != op) {
int x = (v[dg][i].first == dp[dg][0] ? dp[dg][2] : dp[dg][1]);
dp[v[dg][i].first][3] = max(dp[dg][3], x) + v[dg][i].second;
int y = ovox(v[dg][i].first, dg);
dr = (dr > y ? y : dr);
}
}
return dr;
}
int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
for(int i = 0; i < n; ++i) {
v[i].clear();
bo[i] = 0;
}
for(int i = 0; i < m; ++i) {
v[a[i]].push_back({b[i], c[i]});
v[b[i]].push_back({a[i], c[i]});
}
int dm = 0;
vector<int> wv;
for(int i = 0; i < n; ++i) {
if(!bo[i]) {
int x = 0;
pair<int, int> p = ovod(x = ovod(i, -1).second, -1);
ve.clear();
ovog(x, -1, 0, p.second);
ve[0] = 0;
int a = p.first;
dm = max(dm, a);
for(int i = 1; i < ve.size(); ++i) {
a = min(a, max(ve[i], p.first - ve[i]));
}
ovoq(i, -1);
int b = ovox(i, -1);
// cout << "[1] " << a << " " << b << "\n";
assert(a == b);
wv.push_back(a = b);
}
}
sort(wv.begin(), wv.end());
reverse(wv.begin(), wv.end());
int dr = 0;
if(wv.size() == 1);
else if(wv.size() == 2) {
dr = wv[0] + wv[1] + l;
} else {
dr = max(wv[0] + wv[1] + l, wv[1] + wv[2] + l + l);
}
return max(dm, dr);
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a[] = {0,8,2,5,5,1,1,10};
int b[] = {8,2,7,11,1,3,9,6};
int c[] = {4,2,4,3,7,1,5,3};
cout << travelTime(12, 8, 2, a, b, c) << endl;
return 0;
}
#endif
