#include "bits/stdc++.h"
#include "swap.h"
using namespace std;
const int maxn = 3e5 + 10;
const int logn = 19;
typedef pair <int, int> pii;
vector <int> g[maxn];
int l[maxn], r[maxn], w[maxn];
int n, m;
int par[maxn];
int deg[maxn];
int dad[maxn];
bool good[maxn];
multiset <int> cont[maxn];
int anc[logn + 1][maxn];
int opt[maxn], dep[maxn];
struct dsu {
int par[maxn];
void init(int sz) {
for(int i = 0; i < sz; i++) {
par[i] = i;
}
}
int root(int x) {
if(par[x] == x) return par[x];
return par[x] = root(par[x]);
}
void join(int x, int y) {
x = root(x);
y = root(y);
if(x != y) {
par[x] = y;
}
}
} T;
int root(int x) {
if(par[x] == x) return x;
return par[x] = root(par[x]);
}
void remove(int x) {
cont[root(x)].erase(cont[root(x)].find(deg[x]));
}
void add(int x) {
cont[root(x)].insert(deg[x]);
}
void join(int x, int y) {
remove(x);
remove(y);
deg[x] += 1;
deg[y] += 1;
add(x);
add(y);
x = root(x);
y = root(y);
if(x != y) {
if(cont[x].size() > cont[y].size()) swap(x, y);
for(int i : cont[x]) cont[y].insert(i);
cont[x].clear();
par[x] = y;
}
}
bool check(int x, int y) {
x = root(x);
y = root(y);
if(x != y) return false;
return not (*cont[x].begin() <= 1 && *cont[x].rbegin() <= 2);
}
void dfs(int x) {
if(good[x]) opt[x] = w[x - n];
for(int i : g[x]) {
dep[i] = 1 + dep[x];
opt[i] = min(opt[i], opt[x]);
dfs(i);
}
}
int lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
for(int i = logn; i >= 0; i--) {
if(dep[y] - (1 << i) >= dep[x]) {
y = anc[i][y];
}
}
if(x == y) return x;
for(int i = logn; i >= 0; i--) {
if(anc[i][x] != anc[i][y]) {
x = anc[i][x];
y = anc[i][y];
}
}
return anc[0][x];
}
int getMinimumFuelCapacity(int X, int Y) {
if(good[lca(X, Y)]) return opt[lca(X, Y)];
else return opt[X] == INT_MAX ? -1 : opt[X];
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
vector <int> ord (m);
for(int i = 0; i < m; i++) {
ord[i] = i;
}
sort(ord.begin(), ord.end(), [&] (int i, int j) {
return W[i] < W[j]; } );
for(int i = 0; i < m; i++) {
l[i] = U[ord[i]];
r[i] = V[ord[i]];
w[i] = W[ord[i]];
}
T.init(n + m);
for(int i = 0; i < n; i++) {
par[i] = i;
deg[i] = 0;
cont[i].clear();
cont[i].insert(0);
}
for(int i = 0; i < m; i++) {
int p = l[i];
int q = r[i];
if(root(p) != root(q)) {
join(p, q);
dad[T.root(p)] = i + n;
dad[T.root(q)] = i + n;
good[i + n] = check(p, q);
T.join(p, i + n);
T.join(q, i + n);
} else {
join(p, q);
dad[T.root(p)] = i + n;
good[i + n] = check(p, q);
T.join(p, i + n);
}
}
int root = n + m - 1;
dad[root] = root;
for(int i = 0; i < n + m; i++) {
anc[0][i] = dad[i];
opt[i] = INT_MAX;
if(i != root) g[dad[i]].push_back(i);
}
for(int i = 1; i <= logn; i++) {
for(int j = 0; j < n + m; j++) {
anc[i][j] = anc[i - 1][anc[i - 1][j]];
}
}
dep[root] = 0;
dfs(root);
}
