#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
const int mxN=1e5+5;
vector<pii> graph[mxN];
ll dist[mxN],r=2e9;
int ep,seen[mxN],good[mxN],st;
vector<int> path;
void dfs(int at,int p){
path.pb(dist[at]);
seen[at]=1;
if(dist[at]>dist[ep])
ep=at;
for(pii &i:graph[at]){
if(i.first!=p){
dist[i.first]=dist[at]+i.second;
dfs(i.first,at);
}
}
}
void get_rad(int at,int p){
if(at==ep)
good[at]=1;
for(pii &i:graph[at]){
if(i.first==p)
continue;
get_rad(i.first,at);
good[at]|=good[i.first];
}
if(good[at]){
mina(r,max(dist[at],dist[ep]-dist[at]));
}
}
void merge(pii &a,pii &b,int L){
if(max(a.first,b.first)>a.second+b.second+L){
if(a.first<b.first)
swap(a,b);
} else if(max(a.first,b.first)<a.second+b.second+L){
int k=a.second+b.second+L;
a.second=min(max(a.second,k-a.second),max(b.second,k-b.second));
a.first=k;
} else{
int k=a.first<b.first?b.second:a.second;
int p=max(a.first,a.second);
a.second=min(min(max(a.second,p-a.second),max(b.second,p-b.second)),k);
a.first=max(a.first,b.first);
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i<M;i++){
graph[A[i]].pb({B[i],T[i]});
graph[B[i]].pb({A[i],T[i]});
}
vector<pii> all;
for(int i=0;i<N;i++){
if(seen[i])
continue;
ep=N;
dfs(i,-1);
path.clear();
dist[ep]=0; st=ep;
dfs(ep,-1);
r=2e9;
get_rad(st,-1);
all.pb({dist[ep],r});
path.clear();
}
pii ans=all[0];
for(int i=1;i<sz(all);i++){
merge(ans,all[i],L);
}
return ans.first;
}
