#include <bits/stdc++.h>
#include <dreaming.h>
using namespace std;
const long long INFll = 1e18;
const int INFii = 1e9;
const long long mod = (long long) 1e9 + 7;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define maxn 110000
//LEMBRAR DE MUDAR
ii n, m, l, d1[maxn], d2[maxn], mark[maxn], pai[maxn], ans;
vector<pair<ii,ii>> g[maxn];
vector<ii> raio;
pair<ii,ii> dia;
void dfs1(ii a, ii ant) {
for(auto b : g[a]) {
if(b.fr == ant) continue;
d1[b.fr] = d1[a] + b.sc;
dia = max(dia,mp(d1[b.fr],b.fr));
dfs1(b.fr, a);
}
}
void dfs2(ii a) {
mark[a] = 1;
for(auto b : g[a]) {
if(mark[b.fr]) continue;
d2[b.fr] = d2[a] + b.sc;
dia = max(dia,mp(d2[b.fr],b.fr));
dfs2(b.fr);
pai[b.fr] = a;
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]) {
n = N;
m = M;
l = L;
for(ii i = 0; i < m; i++) {
g[A[i]].pb(mp(B[i],T[i]));
g[B[i]].pb(mp(A[i],T[i]));
}
ans = 0;
for(ii i = 0; i < n; i++) {
if(!mark[i]) {
d1[i] = 0;
dia = mp(0,i);
dfs1(i,i);
ii aux = dia.sc;
d2[aux] = 0;
dia = mp(0,aux);
dfs2(aux);
ii rai = INFii;
ans = max(ans, dia.fr);
ii a = dia.sc;
while(true) {
rai = min(rai, max(dia.fr - d2[a],d2[a]));
if(a == aux) break;
a = pai[a];
}
raio.pb(rai);
}
}
sort(raio.begin(),raio.end());
ii r1 = raio.back();
raio.pop_back();
ii r2 = -INFii;
ii r3 = -INFii;
if(!raio.empty()) {
r2 = raio.back() + l;
raio.pop_back();
}
if(!raio.empty()) {
r3 = raio.back() + l;
}
ans = max({ans, r1+r2, r2+r3});
return ans;
}
