#include "swap.h"
#include <bits/stdc++.h>
namespace operators
{
template <typename T1, typename T2>
std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
{
in >> x.first >> x.second;
return in;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
{
out << x.first << " " << x.second;
return out;
}
template <typename T1>
std::istream &operator>>(std::istream &in, std::vector<T1> &x)
{
for (auto &i : x)
in >> i;
return in;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
}
// name spaces
using namespace std;
using namespace operators;
// end of name spaces
// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines
const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;
vector<pair<int, pii>> edges;
struct DSU
{
vector<int> p;
void init(int n)
{
p.resize(n);
for (int i = 0; i < n; ++i)
p[i] = i;
}
int getRoot(int a)
{
return p[a] == a ? a : p[a] = getRoot(p[a]);
}
} dsu;
int n, m;
vector<vector<int>> tree, jump;
vector<int> good, cost, tin, tout;
int timer = 0;
void dfs(int v, int pr, int curCost)
{
tin[v] = ++timer;
if (good[v])
curCost = cost[v];
cost[v] = curCost;
jump[v][0] = pr;
for (int i = 1; i < 20; ++i)
jump[v][i] = jump[jump[v][i - 1]][i - 1];
for (auto tov : tree[v])
dfs(tov, v, curCost);
tout[v] = ++timer;
}
bool isP(int pr, int v)
{
return tin[pr] <= tin[v] and tout[v] <= tout[pr];
}
int lca(int v, int u)
{
if (isP(v, u))
return v;
if (isP(u, v))
return u;
for (int i = 19; i >= 0; --i)
if (!isP(jump[v][i], u))
v = jump[v][i];
return jump[v][0];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
tree.resize(N + M);
jump.resize(N + M, vector<int>(20));
good.resize(N + M);
cost.resize(N + M);
tin.resize(N + M);
tout.resize(N + M);
dsu.init(N + M);
n = N;
m = M;
for (int i = 0; i < M; ++i)
edges.pb({W[i], {U[i], V[i]}});
sort(all(edges));
vector<int> deg(N, 0);
int cnt = 0;
for (auto [w, e] : edges)
{
auto [v, tov] = e;
deg[v]++;
deg[tov]++;
bool isGood = (deg[v] >= 3 or deg[tov] >= 3);
v = dsu.getRoot(v);
tov = dsu.getRoot(tov);
isGood |= (good[v] or good[tov]);
tree[N + cnt].pb(v);
dsu.p[v] = dsu.p[tov] = N + cnt;
if (v != tov)
tree[N + cnt].pb(tov);
else
isGood = true;
cost[N + cnt] = w;
good[N + cnt] = isGood;
cnt++;
}
dfs(N + M - 1, N + M - 1, BIG);
}
int getMinimumFuelCapacity(int X, int Y)
{
int cV = lca(X, Y);
if (cost[cV] == BIG)
return -1;
return cost[cV];
}
// //////////////////////////////
// #include "swap.h"
// #include <cassert>
// #include <cstdio>
// #include <string>
// #include <vector>
// int main()
// {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> U(M), V(M), W(M);
// for (int i = 0; i < M; ++i)
// {
// assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// }
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> X(Q), Y(Q);
// for (int i = 0; i < Q; ++i)
// {
// assert(2 == scanf("%d %d", &X[i], &Y[i]));
// }
// init(N, M, U, V, W);
// std::vector<int> minimum_fuel_capacities(Q);
// for (int i = 0; i < Q; ++i)
// {
// minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
// }
// for (int i = 0; i < Q; ++i)
// {
// printf("%d\n", minimum_fuel_capacities[i]);
// }
// return 0;
// }
