/***********************************************
* auth: tapilyoca *
* date: 04/07/2025 at 08:59:48 *
* dots: https://github.com/tapilyoca/dotilyoca *
***********************************************/
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const long long MOD = 1e9+7;
// using ll = long long;
using ll = int;
using vll = vector<ll>;
using pll = pair<ll,ll>;
using str = string;
#define dbg(x) cerr << #x << ": " << x << endl;
/***********************************************/
pll getDiameter(ll &N, int at, vector<vector<pll>> &adj, vector<bool> &gvis){
// vll dists(N+1,0);
map<ll,ll> dists;
dists[at] = 0;
queue<ll> q;
q.push(at);
// vector<bool> vis(N+1,0);
map<ll,bool> vis;
ll mx = 0;
ll mxnode = at;
vis[at] = 1;
while(!q.empty()){
ll curr = q.front();
q.pop();
for(pll p : adj[curr]){
ll v = p.first;
if(vis[v]) continue;
vis[v] = 1;
gvis[v] = 1;
q.push(v);
dists[v] = dists[curr] + p.second;
if(dists[v] > mx){
mx = dists[v];
mxnode = v;
}
}
}
if(vis.size() == 1){
return {0,at};
}
vis.clear();
dists.clear();
// for(auto itr = dists.begin(); itr != dists.end(); itr++){
// cerr << itr->first << " " << itr->second << endl;
// }
q.push(mxnode);
dists[mxnode] = 0;
vis[mxnode] = 1;
ll out = 0;
ll root = 0;
while(!q.empty()){
ll curr = q.front();
q.pop();
for(pll p : adj[curr]){
ll v = p.first;
if(vis[v]) continue;
vis[v] = 1;
q.push(v);
dists[v] = dists[curr] + p.second;
if(dists[v] > out){
out = dists[v];
root = v;
}
}
}
// now to get radius
// want path on the diameter
// root at stuff
map<ll,ll> parent;
q.push(root);
parent[root] = root;
while(!q.empty()){
ll curr = q.front();
q.pop();
for(pll p : adj[curr]){
ll v = p.first;
if(v == parent[curr]) continue;
parent[v] = curr;
q.push(v);
}
}
if(parent[mxnode] == root or parent[mxnode] == mxnode){
return {out,root};
}
ll radius = out;
ll radiusnode = mxnode;
for(ll curr = mxnode; curr != parent[curr]; curr = parent[curr]){
if(abs(dists[curr] - out/2) < radius){
radius = abs(dists[curr] - out/2);
radiusnode = curr;
}
}
// dbg(root);
// dbg(mxnode);
// dbg(dists[radiusnode]);
// dbg(dists[mxnode]);
// dbg(dists[root] - dists[radiusnode]);
return{max(dists[radiusnode], dists[root] - dists[radiusnode]),radiusnode};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
vector<vector<pll>> adj(N+1);
for(int i = 0; i < M; i++){
adj[B[i]].push_back({A[i],T[i]});
adj[A[i]].push_back({B[i],T[i]});
}
ll compCount = (N-1)-M+1;
vector<ll> diameters(compCount+10,0);
vector<ll> radii(compCount+10,0);
vector<bool> vis(N+1,0);
ll currComp = -1;
ll mxWeight = 0;
ll mxInQuestion = 0;
for(int i = 0; i < N; i++){
if(vis[i]) continue;
vis[i] = 1;
currComp++;
pair<ll,ll> temp = getDiameter(N,i,adj,vis);
radii[currComp] = temp.second; // poorly named, this is the node
diameters[currComp] = temp.first; // poorly named, this is the radius
if(diameters[currComp] > mxWeight){
mxWeight = diameters[currComp];
mxInQuestion = radii[currComp];
}
// cerr << "CENTER OF " << currComp << " IS " << radii[currComp] << " WITH " << diameters[currComp] << endl;
}
// cerr << "HEAVIEST IS " << mxInQuestion << " WITH " << mxWeight << endl;
for(int i = 0; i < compCount; i++){
if(radii[i] == mxInQuestion) continue;
adj[radii[i]].push_back({mxInQuestion,L});
adj[mxInQuestion].push_back({radii[i],L});
// cerr << "ADDED FROM " << radii[i] << " TO " << mxInQuestion << endl;
}
// final diameter search
vis.assign(N+1,0);
vll dists(N+1,0);
queue<ll> q;
q.push(0);
vis[0] = 1;
ll mxnode = 0;
ll mxdist = 0;
while(!q.empty()){
ll curr = q.front();
q.pop();
for(pll tmp : adj[curr]){
ll v = tmp.first;
if(vis[v]) continue;
vis[v] = 1;
q.push(v);
dists[v] = dists[curr] + tmp.second;
if(dists[v] > mxdist){
mxdist = dists[v];
mxnode = v;
}
}
}
// dbg(mxnode);
vis.assign(N+1,0);
vis[mxnode] = 1;
ll diameter = 0;
dists.assign(N+1,0);
q.push(mxnode);
while(!q.empty()){
ll curr = q.front();
q.pop();
for(pll tmp : adj[curr]){
ll v = tmp.first;
if(vis[v]) continue;
vis[v] = 1;
q.push(v);
dists[v] = dists[curr] + tmp.second;
if(dists[v] > diameter){
diameter = dists[v];
}
}
}
return diameter;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, l;
cin >> n >> m >> l;
ll a[m], b[m], c[m];
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i];
}
cout << travelTime(n,m,l,a,b,c) << endl;
return 0;
}
