#include "swap.h"
#include <stdio.h>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
#define mp make_pair
#define f first
#define s second
#define pb push_back
const int maxn = 1e6 + 200;
int subtask2 = 1, subtask1 = 1, cycle = 0;
int used[maxn], p[maxn], sz[maxn], is[maxn], deg[maxn];
multiset<int> setik;
vector<pair<int, int>> g[maxn];
vector<int> g2[maxn];
int ver, reb;
vector<pair<int, pair<int, int>>> kektor;
int get(int v){
if (v == p[v])
return v;
return p[v] = get(p[v]);
}
void unite(int a, int b){
a = get(a), b = get(b);
if (a == b){
is[a] |= 1;
return;
}
if (sz[a] > sz[b])
swap(a, b);
p[a] = b;
sz[b] += sz[a];
is[b] |= is[a];
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
for (int i = 0; i < m; ++i){
int x = u[i], y = v[i];
g[x].pb(mp(y, w[i]));
g[y].pb(mp(x, w[i]));
kektor.pb(mp(w[i], mp(x, y)));
}
for (auto it : u){
subtask2 &= (it == 0);
}
subtask2 &= (m == n - 1);
for (auto it : w){
setik.insert(it);
}
for (int i = 1; i <= n; ++i){
int sz2 = (int)g[i].size();
subtask1 &= (sz2 <= 2);
}
ver = n, reb = m;
for (int i = 0; i < n; ++i){
p[i] = i, sz[i] = 1;
}
sort(kektor.begin(), kektor.end());
}
int getMinimumFuelCapacity(int x, int y) {
if (subtask2 == 1){
if (x == 0){
int cur = g[y][0].s;
setik.erase(setik.find(cur));
int sz2 = (int)setik.size();
if (sz2 == 0){
setik.insert(cur);
return -1;
}
sz2 -= 1;
int cur2 = *setik.begin();
setik.erase(setik.find(cur2));
if (sz2 == 0){
setik.insert(cur);
setik.insert(cur2);
return -1;
}
sz2 -= 1;
int cur3 = *setik.begin();
setik.insert(cur);
setik.insert(cur2);
return max({cur, cur2, cur3});
}
int cur = g[x][0].s;
int cur2 = g[y][0].s;
setik.erase(setik.find(cur));
setik.erase(setik.find(cur2));
if ((int)setik.size() == 0){
setik.insert(cur);
setik.insert(cur2);
return -1;
}
int cur3 = *setik.begin();
setik.insert(cur);
setik.insert(cur2);
return max({cur, cur2, cur3});
}
if (subtask1 == 1){
if (reb == ver - 1){
return -1;
}
else{
return *setik.rbegin();
}
}
for (int i = 0; i < ver; ++i){
p[i] = i, sz[i] = 1, is[i] = 0;
deg[i] = 0;
}
for (auto it : kektor){
pair<int, pair<int, int>> cur = it;
int xu = cur.s.f, yu = cur.s.s;
deg[xu] += 1;
deg[yu] += 1;
int root = get(xu), root2 = get(yu);
is[root] |= (deg[xu] >= 3);
is[root2] |= (deg[yu] >= 3);
unite(xu, yu);
if (get(x) == get(y) && is[get(x)]){
return cur.f;
}
}
return -1;
}
