#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pair<int,int> > v[100010];
vector<pair<int,int> >group;
vector<bool> vis(100010,0);
vector<int> distA(100010,0),distB(100010,0);//profondita;
void dist(int pos){
priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int > >,greater<pair<pair<int,int>,int> > >q;
q.push({{0,pos},-1});
vector<int> y;
int A=pos;
while(!q.empty()){
int p=q.top().first.second;
int d=q.top().first.first;
int prec=q.top().second;
q.pop();
y.push_back(p);
vis[p]=1;
A=p;
for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
}
q.push({{0,A},-1});
int B=A;
while(!q.empty()){
int p=q.top().first.second;
int d=q.top().first.first;
int prec=q.top().second;
q.pop();
B=p;
distA[p]=d;
for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
}
q.push({{0,B},-1});
while(!q.empty()){
int p=q.top().first.second;
int d=q.top().first.first;
int prec=q.top().second;
q.pop();
distB[p]=d;
for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
}
int mi=1e9;
int best;
for(int x:y){
if(max(distA[x],distB[x])<mi){
mi=max(distA[x],distB[x]);
best=x;
}
}
group.push_back({mi,best});
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for(int i=0;i<M;i++){
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<N;i++){
if(vis[i]==0)dist(i);
}
sort(group.begin(),group.end(),greater<pair<int,int> >());
for(int i=1;i<group.size();i++){
int a=group[0].second;
int b=group[i].second;
v[a].push_back({b,L});
v[b].push_back({a,L});
}
priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int > >,greater<pair<pair<int,int>,int> > >q;
q.push({{0,0},-1});
int f=0;
while(!q.empty()){
int p=q.top().first.second;
int d=q.top().first.first;
int prec=q.top().second;
q.pop();
f=p;
for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
}
q.push({{0,f},-1});
int z=0;
while(!q.empty()){
int p=q.top().first.second;
int d=q.top().first.first;
int prec=q.top().second;
q.pop();
z=d;
distA[p]=d;
for(auto x:v[p])if(x.first!=prec)q.push({{d+x.second,x.first},p});
}
return z;
}
/*
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
*//*
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main(){
int N, M, L, i;
int res;
res = scanf("%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = scanf("%d%d%d", &A[i], &B[i], &T[i]);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}*/
