//#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector< pair<int, int> > Graph[100009];
vector< bool > v(100009, false);
vector< int > ans(100009);
int Maxi = 0;
int maxi = -1;
int Last = 0;
void DFS(int node, int last, int dist){
// cout << node << ' ' << last << endl;
if(dist > Maxi){
Maxi = dist;
Last = node;
}
v[node] = true;
for(auto a : Graph[node]){
if(a.first != last){
DFS(a.first, node,dist+a.second);
}
}
}
vector<int> diste(100009);
int radius;
void Radius(int node, int last, int dist){
diste[node] = max(diste[node], dist);
for(auto a : Graph[node]){
if(a.first != last){
Radius(a.first, node, dist+a.second);
}
}
}
void R(int node, int last, int dist, int diam){
if(diste[node] == diam/2){
radius = diam/2;
return;
}
if(diste[node] < diam/2){
radius = min(max(diste[last], diam-diste[last]), max(diste[node], diam-diste[node]));
return ;
}
for(auto a : Graph[node]){
if(a.first != last){
R(a.first, node, dist+a.second, diam);
}
}
}
int F(int a){
// cout << a << endl;
Maxi = -1;
DFS(a,-1,0);
int A = Last;
// cout << A << endl;
Maxi = -1;
DFS(A,-1,0);
//cout << A << ' ' << "Diameter " << Maxi << endl;
maxi = max(Maxi, maxi);
int B = Last;
int diam = Maxi;
//cout << "Between node " << A << " and " << B << ' ' << diam << endl;
for(int i = 0; i < 100009; i++){
diste[i] = -1;
}
Radius(A, -1,0);
radius = 0;
R(B,-1,0,diam);
//cout << radius << endl;
return radius;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++){
Graph[A[i]].push_back(make_pair(B[i], T[i]));
Graph[B[i]].push_back(make_pair(A[i], T[i]));
}
int t = 0;
for(int i = 0; i < N; i++){
if(!v[i]){
ans[t++] = F(i);//FUNCTION
}
}
sort(ans.begin(), ans.begin()+t);
reverse(ans.begin(), ans.begin()+t);
if(t > 1){
maxi = max(maxi, ans[0]+ans[1]+L);
if(t > 2){
maxi = max(maxi, ans[1]+ans[2]+2*L);
}
}
return maxi;
}
int main(){
int n, m, l;
cin >> n >> m >> l;
int a[m];
int b[m];
int t[m];
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> t[i];
}
cout << travelTime(n,m,l,a,b,t) << endl;
}
/*
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
/tmp/ccZmp80a.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccrb3JAd.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccrb3JAd.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
