#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
int tim;
int p[300200];
int s[300200];
int su[300200];
int t1[300200];
int t2[300200];
int tin[300200];
int tout[300200];
int st;
int cnt[300200];
int up[300200][23];
int can[300200][23];
vector < int > v[300200];
int get2( int x )
{
return (p[x] == x ? x : p[x] = get2(p[x]));
}
void merg( int x , int y , int w )
{
cnt[x] += 1 , cnt[y] += 1;
int px = get2( x );
int py = get2( y );
su[st] = w;
if( cnt[x] >= 3 || cnt[y] >= 3 )t1[st] = 1;
if( px == py ){
v[st].push_back(px);
t1[st] |= t1[px];
t2[st] = t2[px] + 1;
s[st] = s[px];
p[px] = st;
}else{
t2[st] = t2[px] + t2[py] + 1;
s[st] = s[px] + s[py];
t1[st] |= (t1[px] | t1[py]);
v[st].push_back(px);
v[st].push_back(py);
p[py] = st;
p[px] = st;
}
st += 1;
}
void dfs( int x , int p )
{
tin[x] = ++tim;
up[x][0] = p;
if( t2[x] >= s[x] ){
t2[x] = 1;
}else t2[x] = 0;
can[x][0] = (t1[p] | t2[p]);
for( int i = 1; i < 23; i++ ){
up[x][i] = up[up[x][i - 1]][i - 1];
can[x][i] = (can[x][i - 1] | can[up[x][i - 1]][i - 1]);
}
for( auto y : v[x] ){
if( y == p )continue;
dfs( y , x );
}
tout[x] = tim;
}
bool upper( int x , int y )
{
return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
st = N;
vector < int > ord;
for( int i = 0; i < M; i++ ){
ord.push_back(i);
}
for( int i = 0; i < 300200; i++ ){
p[i] = i;
s[i] = 1;
}
sort( ord.begin() , ord.end() , [&](int i , int j){
return W[i] < W[j];
});
for( int i = 0; i < M; i++ ){
merg( U[ord[i]] , V[ord[i]] , W[ord[i]] );
}
st -= 1;
dfs( st , st );
}
int get( int x , int y )
{
if( upper( x , y ) )return x;
if( upper( y , x ) )return y;
for( int i = 22; i >= 0; i-- ){
if( !upper( up[x][i] , y ) ){
x = up[x][i];
}
}
return up[x][0];
}
int get1( int x )
{
for( int i = 22; i >= 0; i-- ){
if( !can[x][i] ){
x = up[x][i];
}
}
return up[x][0];
}
int getMinimumFuelCapacity(int X, int Y)
{
if( (t1[st] | t2[st]) == 0 ){
return -1;
}
int f = get( X , Y );
if( (t1[f] | t2[f]) ){
return su[f];
}else{
return su[get1( f )];
}
}
