#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
#include "dreaming.h"
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
int A[MAX_N];
int B[MAX_N];
int T[MAX_N];
const ll N=1e5+5,INF=1e18;
ll cnt,ans,ind;
ll fix[N];
vector <pair <int,int> > v[N],path;
void dfs(int x,int cur){
fix[x]=cnt;
if (cur>ans){
ans=cur;
ind=x;
}
int y=0;
for (int i=0; i<v[x].size(); i++){
if (fix[v[x][i].f]==cnt) continue;
dfs(v[x][i].f,cur+v[x][i].s);
}
}
bool dfs2(ll a,int b,ll c){
fix[a]=3; path.pb(mp(a,c));
if (a==b) return 1;
for (int i=0; i<v[a].size(); i++){
if (fix[v[a][i].f]==3) continue;
if (dfs2(v[a][i].f,b,v[a][i].s)==1) return 1;
}
path.pop_back(); return 0;
}
int travelTime(int n, int m, int L, int a[], int b[], int t[]) {
for (int i=0; i<m; i++){
v[a[i]].pb(mp(b[i],t[i]));
v[b[i]].pb(mp(a[i],t[i]));
}
vector <ll> d;
d.clear(); ll z,x; ll mx=0;
for (int i=0; i<n; i++){
if (fix[i]==0){
ans=-1; cnt=1;
dfs(i,0);
int idx1=ind; cnt=2;
ans=-1;
dfs(ind,0);
int idx2=ind;
path.clear();
// cout<<i<<" "<<idx1<<" "<<idx2<<endl;
bool ook=dfs2(idx1,idx2,0);
ll sum=0;
ll g=1e9;
x=0;
z=0;
for (int i=0; i<path.size(); i++) z+=path[i].s;
mx=max(mx,z);
for (int i=0; i<path.size(); i++){
sum+=path[i].s;
x=max(sum,z-sum);
g=min(g,x);
}
// cout<<g<<endl;
d.pb(g);
}
}
sort(d.begin(),d.end());
z=d.size();
//for (int i=0; i<d.size(); i++) cout<<d[i]<<" "; cout<<endl;
if (z==1) x=d[0]; else if (z==2) x=d[0]+d[1]+L; else
x=max(d[z-1]+d[z-2]+L,d[z-2]+d[z-3]+2*L);
x=max(x,mx);
return x;
}
/*
int main() {
int N, M, L, i;
int res;
cin >> N >> M >> L;
for (i = 0; i < M; i++)
cin >> A[i] >> B[i] >> T[i];
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
/*
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
*/
