#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define FORE(i,a) for(auto&i:a)
#define rep(i,a,b,z) for(int i=(a),_b=(b),_z=(z);i<=_b;i+=_z)
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(),a.end()
#define fs first
#define sc second
typedef pair<int,int> ii;
const int nmax=100010;
int f[nmax],f2[nmax],g[nmax],vst[nmax];
vector<ii>adj[nmax];
void dfs(int u, int p=-1)
{
vst[u]=*vst;
f[u]=f2[u]=0;
FORE(x,adj[u]){
if(x.sc==p)continue;
dfs(x.sc,u);
if(f[u]<f[x.sc]+x.fs){
f2[u]=f[u];
f[u]=f[x.sc]+x.fs;
}
else if(f2[u]<f[x.sc]+x.fs)
f2[u]=f[x.sc]+x.fs;
}
}
void dfs2(int u, int p=-1)
{
FORE(x,adj[u]){
if(x.sc==p)continue;
if(f[u]==f[x.sc]+x.fs)g[x.sc]=max(g[u],f2[u])+x.fs;
else g[x.sc]=max(g[u],f[u])+x.fs;
dfs2(x.sc,u);
}
}
int calc(int n, int l, vector<int>& a)
{
if(n==1)return a[1];
if(n==2)return a[1]+a[2]+l;
sort(a.begin()+1,a.end(),greater<int>());
return min({
max({a[1]+a[2]+l,a[1]+a[3]+l,a[2]+a[3]+l+l}),
max({a[2]+a[1]+l,a[2]+a[3]+l,a[1]+a[3]+l+l}),
max({a[3]+a[1]+l,a[3]+a[2]+l,a[1]+a[2]+l+l})
});
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
FOR(i,0,M-1){
++A[i],++B[i];
adj[A[i]].push_back({T[i],B[i]});
adj[B[i]].push_back({T[i],A[i]});
}
FOR(i,1,N)if(!vst[i])++*vst,dfs(i),dfs2(i);
FOR(i,1,N)f[i]=max(f[i],g[i]);
vector<int>a(*vst+1,0x3f3f3f3f);
FOR(i,1,N)a[vst[i]]=min(a[vst[i]],f[i]);
f[0]=calc(*vst,L,a);
return *max_element(f,f+1+N);
}
