#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define MAX 100005
using ll = long long;
vector<pair<ll,int>> listaadj[MAX];
bool calculado[MAX];
vector<ll> centros;
int filhos[MAX];
ll distancias[MAX];
ll distlegal[MAX][2];
vector<int> arvoreatual;
ll maiorintra = 0;
void contaarvore(int x,int pai){
arvoreatual.push_back(x);
calculado[x] = 1;
for(auto v : listaadj[x]){
if(v.second == pai) continue;
contaarvore(v.second,x);
}
}
void dfs(int x,int pai,int modo){
for(auto v : listaadj[x]){
if(v.second == pai) continue;
distlegal[v.second][modo] = distlegal[x][modo] + v.first;
dfs(v.second,x,modo);
}
}
void calcularcentro(int x){
distlegal[x][0] = 0;
contaarvore(x,-1);
dfs(x,-1,0);
ll maiordist = 0,maiorid = x;
for(auto v : arvoreatual){
if(distlegal[v][0] > maiordist){
maiordist = distlegal[v][0];
maiorid = v;
}
}
distlegal[maiorid][0] = 0;
dfs(maiorid,-1,0);
ll maiordist2 = 0,maiorid2 = maiorid;
for(auto v : arvoreatual){
if(distlegal[v][0] > maiordist2){
maiordist2 = distlegal[v][0];
maiorid2 = v;
}
}
distlegal[maiorid2][1] = 0;
maiorintra = max(maiorintra,maiordist2);
dfs(maiorid2,-1,1);
ll menortotal = INT64_MAX;
for(auto v : arvoreatual){
menortotal = min(menortotal,max(distlegal[v][0],distlegal[v][1]));
}
vector<int> temp;
swap(temp,arvoreatual);
centros.push_back(menortotal);
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i = 0; i < M; i++){
int a = A[i],b = B[i],w = T[i];
listaadj[a].push_back({w,b});
listaadj[b].push_back({w,a});
}
for(int i = 0; i < N; i++){
if(calculado[i])continue;
calcularcentro(i);
}
sort(centros.begin(),centros.end());
int tamcentros = centros.size();
if(tamcentros == 1){
return(maiorintra);
}else if(tamcentros == 2){
return(max(centros[tamcentros - 1] + centros[tamcentros - 2] + L,maiorintra));
}else{
return(max(max(centros[tamcentros - 1] + centros[tamcentros - 2] + L, centros[tamcentros - 2] + centros[tamcentros - 3] + (2 * L)),maiorintra));
}
}
