#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<bool> seen;
vector<vector<pair<int,int>>> g;
void calc(int i, unordered_map<int,int>& d){
queue<pair<int,int>> q;
q.push({i, 0});
while (!q.empty()){
int cur = q.front().first, dist = q.front().second;
q.pop();
seen[cur] = true;
d[cur] = dist;
for (pair<int,int> next : g[cur]){
if (d.find(next.first) == d.end()) q.push({next.first, dist+next.second});
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
g.resize(N);
for (int i=0; i<M; i++){
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<int> rs;
seen.resize(N, false);
int ld = 0;
for (int i=0; i<N; i++){
if (seen[i]) continue;
unordered_map<int,int> d1, d2;
calc(i, d1);
int bsf = -1, bo=i;
for (auto &[i, d] : d1){
if (d > bsf){
bsf = d;
bo = i;
}
}
d1.clear();
calc(bo, d1);
bsf = -1;
for (auto &[i, d] : d1){
ld = max(ld, d);
if (d > bsf){
bsf = d;
bo = i;
}
}
calc(bo, d2);
int res = pow(10, 9);
for (auto &[i, d] : d1) res = min(res, max(d, d2[i]));
rs.push_back(res);
}
if (M == N-1) return ld;
sort(rs.begin(), rs.end());
reverse(rs.begin(), rs.end());
int res = ld;
res = max(res, rs[0]+rs[1]+L);
if (rs.size() > 2) res = max(res, rs[1]+rs[2]+2*L);
return res;
}
