#include <bits/stdc++.h>
#include "dreaming.h"
#define MAXN 100002
#define pb push_back
typedef long long ll;
using namespace std;
vector <pair<int, int>> viz[MAXN];
int visitado[MAXN];
ll auxNode, auxDist;
int anc[MAXN];
int distAnc[MAXN];
void maisLonge(int atual, int pai, ll dist) {
visitado[atual] = 1;
anc[atual] = -1;
distAnc[atual] = 0;
if(dist > auxDist) auxDist = dist, auxNode = atual;
for(auto [p, d]:viz[atual]) {
if(p == pai) continue;
maisLonge(p, atual, dist+d);
}
}
void maisLongeAtualizaPai(int atual, int pai, ll dist) {
if(dist > auxDist) auxDist = dist, auxNode = atual;
for(auto [p, d]:viz[atual]) {
if(p == pai) continue;
anc[p] = atual;
distAnc[p] = d;
maisLongeAtualizaPai(p, atual, dist+d);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < MAXN; i++) {
viz[i].clear();
visitado[i] = 0;
}
for(int i = 0; i < M; i++) {
viz[A[i]].pb({B[i], T[i]});
viz[B[i]].pb({A[i], T[i]});
}
ll maiorDiametro = 0;
ll mr1 = 0, mr2 = 0, mr3 = 0;
for(int i = 0; i < N; i++) {
if(visitado[i]) continue;
auxNode = i, auxDist = 0;
maisLonge(i, i, 0);
int ponta1 = auxNode;
auxNode = i, auxDist = 0;
anc[ponta1] = ponta1; distAnc[ponta1] = 0;
maisLongeAtualizaPai(ponta1, ponta1, 0);
int ponta2 = auxNode;
ll diametro = auxDist;
ll raioAtual = 0;
ll menorMaiorRaio = LLONG_MAX;
while(ponta1 != ponta2) {
raioAtual += distAnc[ponta2];
menorMaiorRaio = min(max(diametro - raioAtual, raioAtual), menorMaiorRaio);
ponta2 = anc[ponta2];
}
maiorDiametro = max(maiorDiametro, diametro);
if(menorMaiorRaio != LLONG_MAX) {
if(menorMaiorRaio > mr3) mr3 = menorMaiorRaio;
if(mr3 > mr2) swap(mr3, mr2);
if(mr2 > mr1) swap(mr1, mr2);
}
}
// if(mr2 == -1) return maiorDiametro;
// if(mr3 == -1) return max({maiorDiametro, mr1 + mr2 + L});
if(M == N-1) return maiorDiametro;
if(M == N-2) return max({maiorDiametro, mr1 + mr2 + L});
return max({maiorDiametro, mr1 + mr2 + L, mr2 + mr3 + 2*L});
}
