#include "dreaming.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
inline constexpr void cmax(int &x, const int &y) {if (x < y) x = y;}
inline constexpr void cmin(int &x, const int &y) {if (x > y) x = y;}
inline constexpr void best(ii &x, const int &y) {
if (x.fi < y) {
x.se = x.fi;
x.fi = y;
} else if (x.se < y) x.se = y;
}
int n, m, l;
struct edge {
int u, v, l;
edge() {}
edge(int _u, int _v, int _l) : u(_u), v(_v), l(_l) {}
} edges[maxn];
int cl[maxn];
int d[maxn];
ii f[maxn]; int g[maxn];
vector<ii> adj[maxn];
ii Find_best(int z) {
vector<int> nodes;
function<void(int, int)> dfs = [&](int u, int dad) {
cl[u] = 1;
nodes.emplace_back(u);
for (auto [v, l] : adj[u])
if (v != dad) {
d[v] = d[u] + l;
dfs(v, u);
best(f[u], f[v].fi+l);
}
};
function<void(int, int)> tfs = [&](int u, int dad) {
for (auto [v, l] : adj[u])
if (v != dad) {
if (f[u].fi == f[v].fi+l) g[v] = max(g[u], f[u].se) + l;
else g[v] = max(g[u], f[u].fi) + l;
tfs(v, u);
}
};
ii cr = {INT_MAX, -1};
dfs(z, 0); tfs(z, 0);
int opt = 0;
for (int i : nodes) {
if (cr.se < d[i]) {
cr.se = d[i];
opt = i;
}
cmin(cr.fi, max(f[i].fi, g[i]));
}
d[opt] = 0;
dfs(opt, 0);
for (int i : nodes) cmax(cr.se, d[i]);
return cr;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N; m = M; l = L;
for (int i = 0; i < m; i++) edges[i] = edge(A[i], B[i], T[i]);
for (int i = 0; i < n; i++) {
cl[i] = g[i] = d[i] = 0;
adj[i].clear();
}
for (int i = 0; i < m; i++) {
auto [u, v, l] = edges[i];
adj[u].emplace_back(v, l);
adj[v].emplace_back(u, l);
}
//Optimal point.. diameter.. ok that's it
multiset<ii> q;
for (int i = 0; i < n; i++) if (!cl[i]) q.insert(Find_best(i));
while (q.size() > 1) {
auto it = q.begin();
ii H1 = *it; ++it;
ii H2 = *it;
q.erase(q.find(H1));
q.erase(q.find(H2));
q.insert(ii{
min(max(H1.fi, H2.fi+l), max(H1.fi+l, H2.fi)),
max({H1.se, H2.se, l + H1.fi + H2.fi})});
}
return q.begin()->se;
}
//18
