#include <iostream>
#include <vector>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 10;
vector<pair<int,int>> nei[N];
int Mx[N][4], Min;
void dfs2(int u, int p){
for (auto [i, w] : nei[u]){
if (i == p)
continue;
if (Mx[i][1] + w == Mx[u][1])
Mx[i][3] = max(Mx[u][3], Mx[u][2]) + w;
else
Mx[i][3] = max(Mx[u][3], Mx[u][1]) + w;
dfs2(i, u);
}
Min = min(Min, max(Mx[u][3], Mx[u][1]));
}
void dfs1(int u, int p){
for (auto [i, w] : nei[u]){
if (i == p)
continue;
dfs1(i, u);
if (Mx[i][1] + w > Mx[u][1])
Mx[u][2] = Mx[u][1], Mx[u][1] = Mx[i][1] + w;
else
Mx[u][2] = max(Mx[u][2], Mx[i][1] + w);
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
for (int i=0;i<m;i++){
nei[B[i]].push_back({A[i], T[i]});
nei[A[i]].push_back({B[i], T[i]});
}
int M1 = 0, M2 = 0, M3 = 0;
for (int i=0;i<n;i++){
if (Mx[i][1] or Mx[i][3])
continue;
Min = 1e9;
dfs1(i, i);
dfs2(i, i);
if (Min > M1)
M3 = M2, M2 = M1, M1 = Min;
else if (Min > M2)
M3 = M2, M2 = Min;
else
M3 = max(M3, Min);
}
if (m == n - 1)
return M1;
return max(M1 + M2 + l, M2 + M3 + l + l);
}
