/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include "dreaming.h"
#include <algorithm>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using namespace std;
#define ln '\n'
#define INFi 1e9
#define INFll 1e18
// #include <algo.hpp>
#ifdef ONPC
#else
#define dbg(...)
#define dbg_out(...)
#endif
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < M; i++) {
int &u = A[i];
int &v = B[i];
int &w = T[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<int> dist(N, false), used(N, false), par(N, -1);
int res = -1;
function<void(int, int, int)> dfs = [&](int v, int pa, int dst) {
dist[v] = dst;
used[v] = true;
par[v] = pa;
if (res == -1 || dst > dist[res]) {
res = v;
}
for (const auto &[u, w] : g[v]) {
if (u == pa)
continue;
dfs(u, v, dst + w);
}
};
// WARNING: dfs den evvel res = -1 elemelisen
res = -1;
vector<int> groups;
for (int i = 0; i < N; i++) {
if (used[i])
continue;
res = -1;
dfs(i, -1, 0);
dfs(res, -1, 0);
vector<int> path;
int cur = res;
while (cur != -1) {
path.push_back(cur);
cur = par[cur];
}
reverse(path.begin(), path.end());
dbg(path);
groups.push_back(path[(path.size() + 1) >> 1]);
}
// dbg(groups);
for (int i = 1; i < groups.size(); i++) {
const int &u = groups[0];
const int &v = groups[i];
g[u].push_back({v, L});
g[v].push_back({u, L});
}
res = -1;
dfs(0, -1, 0);
dfs(res, -1, 0);
dbg(groups);
// cout << dist[res] << ln;
return dist[res];
}
// Attack on titan<3
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
