#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
const int INF = 1000000010;
int n, m;
int w[MAXN];
int ord[MAXN];
int minTime[MAXN];
int anc[MAXN], tW[MAXN], degree[MAXN];
vector<int> nodes[MAXN];
bool cmp(int i, int j) { return w[i] < w[j]; }
int find(int cur)
{
if( anc[cur] == cur ) return cur;
return find( anc[cur] );
}
void update(int i, int curW)
{
if( curW == INF ) return;
if( minTime[i] != INF ) return;
for(int k = 0 ; k < (int)nodes[i].size() ; k++)
minTime[ nodes[i][k] ] = curW;
}
void join(int i, int j, int curW)
{
degree[i]++; degree[j]++;
bool flip = ( degree[i] >= 3 || degree[j] >= 3 );
i = find(i), j = find(j);
if( i == j ) flip = true;
if( flip )
{
update( i , curW );
update( j , curW );
}
if( i == j ) return;
bool isSpecial = ( minTime[i] != INF || minTime[j] != INF );
if( isSpecial )
{
update( i , curW );
update( j , curW );
}
if( (int)nodes[i].size() < (int)nodes[j].size() )
swap( i , j );
anc[j] = i;
tW[j] = curW;
while( !nodes[j].empty() )
{
nodes[i].push_back( nodes[j].back() );
nodes[j].pop_back();
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
n = N; m = M;
for(int i = 0 ; i < n ; i++)
{
anc[i] = i;
nodes[i].push_back( i );
minTime[i] = tW[i] = INF;
}
for(int i = 0 ; i < m ; i++)
w[i] = W[i];
iota( ord , ord + m , 0 );
sort( ord , ord + m , cmp );
for(int i = 0 ; i < m ; i++)
join( U[ ord[i] ] , V[ ord[i] ] , W[ ord[i] ] );
}
int getMinimumFuelCapacity(int X, int Y)
{
if( minTime[X] == INF ) return -1;
int ans = minTime[X];
while( X != Y )
{
if( tW[X] > tW[Y] )
swap( X , Y );
ans = max( ans , tW[X] );
X = anc[X];
}
return ans;
}
