#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
const int INF = 2e9;
const int mxN = 1e5 + 5000;
vector<pair<int,int>> adj[mxN];
bool vis[mxN];
int tot=0;
void dfs(int u,int par,int w,int &c){
c=min(c,max(w,tot-w));
vis[u]=1;
for(auto it:adj[u]){
if(it.fi^par){
dfs(it.fi,u,w+it.se,c);
}
}
}
void calc_tot(int u,int par){
for(auto it:adj[u]){
if(it.fi^par){
tot+=it.se;
calc_tot(it.fi,u);
}
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i=0;i<N+5;++i){
adj[i].clear();
vis[i]=0;
tot=0;
}
int t[3];
for(int i=0;i<M;++i) adj[A[i]].pb({B[i],T[i]}),adj[B[i]].pb({A[i],T[i]});
int done=0,ans=L;
for(int i=0;i<N&&done<2;++i){
if(!vis[i]&&adj[i].size()<=1){
tot=0;
calc_tot(i,-1);
int current=INF;
dfs(i,-1,0,current);
ans+=current;
t[done]=tot;
++done;
}
}
ans=max({ans,t[0],t[1]});
return ans;
}
