#include <bits/stdc++.h>
//#include "dreaming.h"
using namespace std;
#define mod 1000000007
#define maxn 100005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
#define mp make_pair
vector<pair<int, ll>> g[maxn];
bool a[maxn];
pair<int, ll> b[maxn][2];
int c[maxn];
queue<pair<int, ll>>q;
ll dfs(int u, int p){
long long mn=INT64_MAX;
for(auto i:g[u]){
if(i.f!=p){
if(b[u][0].f!=i.f){
if(b[u][0].s+i.s>b[i.f][0].s){
b[i.f][1]=b[i.f][0];
b[i.f][0]=mp(u,b[u][0].s+i.s);
}else if(b[u][0].s+i.s>b[i.f][1].s){
b[i.f][1]=mp(u,b[u][0].s+i.s);
}
}else if(b[u][1].s+i.s>b[i.f][0].s){
b[i.f][1]=b[i.f][0];
b[i.f][0]=mp(u,b[u][1].s+i.s);
}else if(b[u][1].s+i.s>b[i.f][1].s){
b[i.f][1]=mp(u,b[u][1].s+i.s);
}
mn=min(mn, dfs(i.f, u));
}
}
return min(mn, b[u][0].s);
}
int travelTime(int N,int M,int L,int *A,int *B,int *T){
for(int i=0; i<M; i++){
g[A[i]].pb(mp(B[i], T[i]));
g[B[i]].pb(mp(A[i], T[i]));
}
vector<ll> v;
for(int i=0; i<N; i++){
if(g[i].size()==0){
v.pb(0);
}else if(g[i].size()==1){
q.push(mp(i, 0));
}
b[i][0].f=b[i][1].f=i;
b[i][1].s=-10000;
c[i]=g[i].size();
}
while(q.size()){
int u=q.front().f;q.pop();
a[u]=1;
if(c[u]==0){
v.pb(dfs(u, u));
continue;
}
for(auto i:g[u]){
if(!a[i.f]){
if(b[u][0].s+i.s>b[i.f][0].s){
b[i.f][1]=b[i.f][0];
b[i.f][0]=mp(u,b[u][0].s+i.s);
}else{
b[i.f][1]=mp(u,b[u][0].s+i.s);
}
c[i.f]--;
if(c[i.f]==1){
q.push(mp(i.f, b[i.f][0].s));
}
}
}
}
sort(v.begin(), v.end(), greater<>());
long long ans=0;
if(v.size()==1){
ans= v[0];
}else if(v.size()==2){
ans= v[0]+L+v[1];
}else{
ans= max(v[0]+L+v[1], v[1]+v[2]+L*2);
}
for(int i=0; i<N; i++){
if(g[i].size()==1){
ans=max(ans, b[i][0].s);
}
}
return ans;
}
/*int main(){
int n,m,k;
cin >> n >> m >> k;
int a[m], B[m],c[m];
for(int i=0; i<n; i++)
cin >> a[i] >> B[i] >> c[i];
cout << travelTime(n,m,k,a,B,c)<<"\n";
}*/
