#include <bits/stdc++.h>
#include "dreaming.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int NN=1e5+5;
int l[NN],d[NN],p[NN];
vector <int> gr[NN];
vector <pair <int,int> >g[NN];
int find_set(int v){
if(l[v]==v)return v;
return l[v]=find_set(l[v]);
}
void union_set(int u,int v){
u=find_set(u);
v=find_set(v);
if(u!=v){
if(gr[v].size()<gr[u].size())swap(u,v);
l[u]=v;
for(auto x : gr[u])gr[v].pb(x);
gr[u].clear();
}
}
void bfs(int v){
queue <int> q;
q.push(v);
while(!q.empty()){
int v=q.front();
q.pop();
for(auto to : g[v]){
if(d[to.ff]==-1){
p[to.ff]=v;
d[to.ff]=d[v]+to.ss;
q.push(to.ff);
}
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<N;i++){
l[i]=i;
gr[i].pb(i);
}
for(int i=0;i<M;i++){
union_set(A[i],B[i]);
g[A[i]].pb({B[i],T[i]});
g[B[i]].pb({A[i],T[i]});
}
vector <int> len;
int ans=0;
for(int i=0;i<N;i++)d[i]=-1;
for(int i=0;i<N;i++){
if(gr[i].size()!=0){
d[gr[i][0]]=0;
bfs(gr[i][0]);
int mx=0,node=gr[i][0];
for(auto x : gr[i]){
if(d[x]>mx){
mx=d[x];
node=x;
}
d[x]=-1;
p[x]=0;
}
d[node]=0;
bfs(node);
mx=0;
int s=node;
for(auto x : gr[i]){
if(d[x]>mx){
mx=d[x];
node=x;
}
}
ans=max(ans,mx);
vector <int> path;
path.pb(node);
while(node!=s){
node=p[node];
path.pb(node);
}
int mn=1e9+5;
for(auto x : path){
mn=min(max(mx-d[x],d[x]),mn);
}
len.pb(mn);
for(auto x : gr[i]){
d[x]=-1;
p[x]=0;
}
}
}
sort(all(len));
for(auto x : len)ans=max(ans,x);
if(len.size()>=2)ans=max(ans,L+len[len.size()-1]+len[len.size()-2]);
if(len.size()>=3)ans=max(ans,2*L+len[len.size()-2]+len[len.size()-3]);
return ans;
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,m,l;
cin>>n>>m>>l;
int 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);
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
Compilation message
/usr/bin/ld: /tmp/cc0WjQrB.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccu1A2aE.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
