#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];
multiset<int> setik;
vector<pair<int, int>> g[maxn];
vector<int> g2[maxn];
int ver, reb;
vector<pair<int, pair<int, int>>> kektor;
void dfs(int v, int p){
used[v] = 1;
for (auto to : g2[v]){
int nx = to;
if (nx != p){
if (used[nx] == 0){
dfs(nx, v);
}
else{
cycle = 1;
}
}
}
}
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)));
// g2[x].pb(y);
// g2[y].pb(x);
}
// dfs(364, -1);
/*for (int i = 0; i < n; ++i){
if (used[i] == 0){
cout << i << '\n';
}
}
cout << used[588];
exit(0);*/
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 sz = (int)g[i].size();
subtask1 &= (sz <= 2);
}
ver = n, reb = m;
sort(kektor.begin(), kektor.end());
/*for (int i = 0; i < m; ++i){
int x = kektor[i].s.f, y = kektor[i].s.s;
g2[x].pb(y);
g2[y].pb(x);
for (int j = 0; j < n; ++j){
used[j] = 0;
}
cycle = 0;
dfs(364, -1);
if (cycle && used[588]){
// cout << i << '\n';
cout << kektor[i].f << '\n';
exit(0);
}
for (int j = 0; j < n; ++j){
int sz = (int)g2[j].size();
if (sz >= 3 && used[j] && used[588]){
cout << kektor[i].f << '\n';
exit(0);
}
}
if (kektor[i].f == 998840){
cout << i << '\n';
cout << "lol\n";
exit(0);
}
if (used[588]){
cout << i << '\n';
exit(0);
}
if (x == 588 || y == 588){
cout << "yes\n";
cout << i << '\n';
exit(0);
}
}*/
}
int getMinimumFuelCapacity(int x, int y) {
if (subtask2 == 1){
if (x == 0){
int cur = g[y][0].s;
setik.erase(setik.find(cur));
int sz = (int)setik.size();
if (sz == 0){
setik.insert(cur);
return -1;
}
sz -= 1;
int cur2 = *setik.begin();
setik.erase(setik.find(cur2));
if (sz == 0){
setik.insert(cur);
setik.insert(cur2);
return -1;
}
sz -= 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){
g2[i].clear();
}
for (int i = 0; i < reb; ++i){
pair<int, pair<int, int>> cur = kektor[i];
int xu = cur.s.f, yu = cur.s.s;
g2[xu].pb(yu);
g2[yu].pb(xu);
cycle = 0;
for (int j = 0; j < ver; ++j){
used[j] = 0;
}
dfs(x, -1);
if (cycle && used[y]){
return cur.f;
}
if (used[y] > 0){
for (int j = 0; j < ver; ++j){
int sz = (int)g2[j].size();
if (sz >= 3 && used[j] > 0){
return cur.f;
}
}
}
}
return -1;
}
