#include <cassert>
#include <cstdio>
#pragma warning(disable : 4996)
#include <map>
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define pll pair<ll,ll>
vi col_v;
vector<vector<pi>> his;
vector<vi> col;
vector<pi> kats;
void uni(int i, int j, int t) {
if (col_v[i] == col_v[j]) {
if (his[i][0].first == -1) {
for (int x : col[col_v[i]]) {
his[x][0] = { t,-1 };
}
}
return;
}
if (col[col_v[i]].size() > col[col_v[j]].size())
swap(i, j);
int c = col_v[j];
int c1 = col_v[i];
if (his[i][0].first != -1) {
if (his[j][0].first == -1) {
for (int x : col[c]) {
his[x][0] = { t,-1 };
}
}
}
else if (his[j][0].first != -1) {
if (his[i][0].first == -1) {
for (int x : col[c1]) {
his[x][0] = { t,-1 };
}
}
}
else if (i == kats[c1].first) {
if (j == kats[c].second) {
kats[c] = { kats[c1].second,kats[c].first };
}
else if (j == kats[c].first) {
kats[c] = { kats[c1].second,kats[c].second };
}
else {
for (int x : col[c1]) {
his[x][0] = { t,-1 };
}
for (int x : col[c]) {
his[x][0] = { t,-1 };
}
}
}
else if (i == kats[c1].second) {
if (j == kats[c].second) {
kats[c] = { kats[c1].first,kats[c].first };
}
else if (j == kats[c].first) {
kats[c] = { kats[c1].first,kats[c].second };
}
else {
for (int x : col[c1]) {
his[x][0] = { t,-1 };
}
for (int x : col[c]) {
his[x][0] = { t,-1 };
}
}
}
else {
for (int x : col[c1]) {
his[x][0] = { t,-1 };
}
for (int x : col[c]) {
his[x][0] = { t,-1 };
}
}
for (int x : col[col_v[i]]) {
col_v[x] = c;
col[col_v[j]].push_back(x);
his[x].push_back({ t,c });
}
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
col_v.resize(N);
his.resize(N);
vector<vi> v;
for (int i = 0; i < N; i++) {
his[i].push_back({ -1,-1 });
his[i].push_back({ 0,i });
kats.push_back( { i, i });
}
col.resize(N);
for (int i = 0; i < N; i++) {
col_v[i] = i;
col[i].push_back(i);
}
for (int i = 0; i < M; i++) {
v.push_back({ W[i],V[i],U[i] });
}
sort(v.begin(), v.end());
for (vi vec : v) {
uni(vec[1], vec[2], vec[0]);
}
}
int getMinimumFuelCapacity(int X, int Y) {
vector<pi> v1 = his[X];
vector<pi> v2 = his[Y];
int s = max(v1[0].first, v2[0].first);
int it1 = v1.size() - 1;
int it2= v2.size() - 1;
if (v1[0].first == -1)
return -1;
while (true) {
it1--;
it2--;
if (v1[it1].second != v2[it2].second || max(v1[it1].first, v2[it2].first) < s ) {
return max(max(v1[it1 + 1].first, v2[it2 + 1].first),s);
}
}
}
