#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 5;
struct info {
int d, da, db;
info() {}
info(int _d, int _da, int _db) : d(_d), da(_da), db(_db) {}
};
info optimize(info u, info v) {
return max(u.da, u.db) < max(v.da, v.db) ? u : v;
}
info merge(info u, info v, int w) {
int dd[6] = {u.d, v.d, u.da + w + v.da, u.da + w + v.db, u.db + w + v.da, u.db + w + v.db};
int mx = *max_element(dd, dd + 6);
info res(mx, 2e9, 2e9);
for (int i = 0; i < 6; i++) {
if (dd[i] == mx) {
if (i == 0) {
res = optimize(res, info(mx, u.da, u.db));
} else if (i == 1) {
res = optimize(res, info(mx, v.da, v.db));
} else if (i == 2) {
res = optimize(res, info(mx, u.da, w + v.da));
res = optimize(res, info(mx, w + u.da, v.da));
} else if (i == 3) {
res = optimize(res, info(mx, u.da, w + v.db));
res = optimize(res, info(mx, w + u.da, v.db));
} else if (i == 4) {
res = optimize(res, info(mx, u.db, w + v.da));
res = optimize(res, info(mx, w + u.db, v.da));
} else if (i == 5) {
res = optimize(res, info(mx, u.db, w + v.db));
res = optimize(res, info(mx, w + u.db, v.db));
}
}
}
return res;
}
struct dsu {
int lab[N];
info fi[N];
dsu() {
memset(lab, -1, sizeof(lab));
for (int i = 0; i < N; i++) {
fi[i] = info(0, 0, 0);
}
}
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
bool unite(int u, int v, int w) {
if ((u = find(u)) == (v = find(v))) {
return false;
}
if (lab[u] > lab[v]) {
swap(u, v);
}
fi[u] = merge(fi[u], fi[v], w);
lab[u] += lab[v];
lab[v] = u;
return true;
}
};
vector<pair<int, int>> g[N];
dsu ds;
int d[N];
int da[N], db[N];
void process(int id) {
queue<int> q;
d[id] = 0;
q.push(id);
int mx = 0;
int j = id;
vector<int> nd;
nd.emplace_back(id);
while (!q.empty()) {
int u = q.front();
q.pop();
for (pair<int, int> e : g[u]) {
int v = e.first;
int w = e.second;
if (d[v] > d[u] + w) {
nd.emplace_back(v);
d[v] = d[u] + w;
q.push(v);
if (d[v] > mx) {
mx = d[v];
j = v;
}
}
}
}
int a = j;
for (int x : nd) {
d[x] = 0x3f3f3f3f;
}
d[j] = 0;
q.push(j);
mx = 0;
int k = j;
while (!q.empty()) {
int u = q.front();
q.pop();
for (pair<int, int> e : g[u]) {
int v = e.first;
int w = e.second;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push(v);
if (d[v] > mx) {
mx = d[v];
k = v;
}
}
}
}
int b = k;
q.push(a);
da[a] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (pair<int, int> e : g[u]) {
int v = e.first;
int w = e.second;
if (da[v] > da[u] + w) {
da[v] = da[u] + w;
q.push(v);
}
}
}
q.push(b);
db[b] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (pair<int, int> e : g[u]) {
int v = e.first;
int w = e.second;
if (db[v] > db[u] + w) {
db[v] = db[u] + w;
q.push(v);
}
}
}
pair<int, int> opt = {2e9, 2e9};
for (int i = 0; i < (int) nd.size(); i++) {
if (max(da[nd[i]], db[nd[i]]) < max(opt.first, opt.second)) {
opt = {da[nd[i]], db[nd[i]]};
}
}
for (int i = 0; i < (int) nd.size() - 1; i++) {
ds.unite(nd[i], nd[i + 1], 0);
}
int root = ds.find(nd.front());
ds.fi[root] = info(mx, opt.first, opt.second);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
memset(d, 0x3f, sizeof(d));
memset(da, 0x3f, sizeof(da));
memset(db, 0x3f, sizeof(db));
for (int i = 0; i < m; i++) {
g[a[i]].emplace_back(b[i], t[i]);
g[b[i]].emplace_back(a[i], t[i]);
}
for (int i = 0; i < n; i++) {
if (d[i] == 0x3f3f3f3f) {
process(i);
}
}
vector<int> c;
for (int i = 0; i < n; i++) {
c.emplace_back(ds.find(i));
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
int ans = 2e9;
int sz = c.size();
vector<int> mx(sz);
int od = 0;
for (int i = 0; i < sz; i++) {
mx[i] = max(ds.fi[c[i]].da, ds.fi[c[i]].db);
od = max(od, ds.fi[c[i]].d);
}
multiset<int> mts;
for (int i = 0; i < sz; i++) {
mts.insert(mx[i] + l);
}
for (int i = 0; i < sz; i++) {
int tmp = od;
mts.erase(mts.find(mx[i] + l));
mts.insert(mx[i]);
if ((int) mts.size() >= 2) {
tmp = max(tmp, *(--mts.end()) + *(--(--mts.end())));
}
ans = min(ans, tmp);
mts.erase(mts.find(mx[i]));
mts.insert(mx[i] + l);
}
return ans;
}
