#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ppb pop_back
#define C continue
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<pi> vpi;
#include "dreaming.h"
ll n,m,k;
vpll v[100009];
map<pll,ll>mp;
ll done[100009];
vll ret,all;
ll mx,id,z;
void dfs1(int node,int p,ll crnt){
done[node]=1;
if(crnt>=mx){
mx=crnt;
id=node;
}
for(auto u:v[node]){
if(u.fi==p)C;
dfs1(u.fi,node,crnt+u.se);
}
}
void dfs2(int node,int p){
done[node]=1;
if(!z)ret.pb(node);
if(node==id){
z=1;
return ;
}
for(auto u:v[node]){
if(u.fi==p)C;
dfs2(u.fi,node);
if(z)return ;
}
if(!z)ret.ppb();
}
int find(){
vll X;
X.resize((int)ret.size());
ll crnt=0;
for(int i=0;i<ret.size();i++){
if(i)crnt+=mp[{ret[i],ret[i-1]}];
X[i]=max(X[i],crnt);
}
crnt=0;
ll timer=ret.size()-1;
for(int i=0;i<ret.size();i++){
if(i)crnt+=mp[{ret[i],ret[i-1]}];
X[timer]=max(X[timer],crnt);
timer--;
}
ll mn=1e9*2;
for(int i=0;i<X.size();i++){
mn=min(mn,X[i]);
}
return mn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N,m=M,k=L;
for(int i=0;i<m;i++){
int a=A[i],b=B[i],c=T[i];
v[a].pb({b,c});
v[b].pb({a,c});
mp[{a,b}]=mp[{b,a}]=c;
}
for(int i=0;i<n;i++){
if(done[i])C;
mx=id=-1;
z=0;
ret.clear();
dfs1(i,i,0);
int xxx=id;
mx=id=-1;
dfs1(xxx,xxx,0);
dfs2(xxx,xxx);
all.pb(find());
}
sort(all.begin(),all.end());
reverse(all.begin(),all.end());
ll mx=0;
if(all.size()==1)mx=all[0];
if(all.size()==2)mx=all[0]+all[1]+L;
if(all.size()>2){
mx=all[0]+all[1]+L;
mx=max(mx,all[1]+all[2]+L+L);
}
return mx;
}
