#include<bits/stdc++.h>
using namespace std ;
#define maxn 250009
#define ll long long
#define pb push_back
#define fi first
#define se second
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
#define TIME (1.0*clock()/CLOCK_PERS_SEC)
const int mod = 1e9+7 ;
const int INF = 1e9 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
void add ( int &a , int b )
{
a += b ;
if ( a >= mod ) a -= mod ;
if ( a < 0 ) a += mod ;
}
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ;}
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ;}
void rf ()
{
freopen("bai1.inp","r",stdin) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow (a,n/2) ;
if ( n % 2 ) return 1ll*res*res%mod*a%mod ;
else return 1ll*res*res%mod ;
}
mt19937 rng(time(0)) ;
//#include "grader.h"
int n , m ;
vi u , v , w ;
int lab [maxn] , deg [maxn] ;
struct shape {
int u , v , w ;
}e[maxn];
bool cmp ( shape u , shape v )
{
return u.w < v.w ;
}
void init ( int N , int M , vi U , vi V , vi W )
{
n = N , m = M ;
for ( int i = 0 ; i < m ; i ++ )
{
U [i] ++ , V [i] ++ ;
e [i+1] = {U[i],V[i],W[i]} ;
}
sort (e+1,e+m+1,cmp) ;
}
int find ( int u )
{
return (lab[u]<0?u:lab[u]=find(lab[u])) ;
}
void uni ( int u , int v )
{
if ((u=find(u)) == (v=find(v))) return ;
if ( lab [u] > lab [v] ) swap (u,v) ;
lab [u] += lab [v] ;
lab [v] = u ;
}
int getMinimumFuelCapacity ( int x , int y )
{
x ++ , y ++ ;
int l = 1 , r = m ;
int res = -1 ;
while ( l <= r )
{
for ( int i = 1 ; i <= n ; i ++ ) lab [i] = -1 , deg [i] = 0 ;
int mid = (l+r)/2 ;
bool ok = false ;
for ( int i = 1 ; i <= mid ; i ++ )
{
if (find(e[i].u) == find(e[i].v) && find(e[i].u) == find(x) && find(e[i].u) == find(y)) ok = true ;
deg [e[i].u] ++ , deg [e[i].v] ++ ;
uni (e[i].u,e[i].v) ;
}
for ( int i = 1 ; i <= n ; i ++ )
{
if ( deg [i] >= 3 && find (i) == find (x) && find (i) == find (y) ) ok = true ;
}
if ( ok == true ) res = e[mid].w , r = mid-1 ;
else l = mid+1 ;
}
return res ;
}
//int main ()
//{
// init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
// cout << getMinimumFuelCapacity(1,2) ;
//}
