#include<bits/stdc++.h>
#include "swap.h"
//#include "grader.cpp"
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}
#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map
umap<int,umap<int,int>>c;
vvi g;
void init(int n, int M,vi U,vi V,vi W){
g.resize(n);
for(int i=0; i<M; i++){
g[U[i]].pb(V[i]);
g[V[i]].pb(U[i]);
c[U[i]][V[i]]=c[V[i]][U[i]]=W[i];
}
}
bool ans;
void dfs(vvi &g,vector<bool>& vis,int src,int par){
vis[src]=1;
for(int nbr:g[src]) {
if(nbr==par)continue;
if(vis[nbr])ans=1;
else dfs(g,vis,nbr,src);
if(g[src].size()>2)ans=1;
}
}
bool ok(int x,int y,int w){
int n=g.size();
vvi gt(n);
for(int i=0; i<n; i++)
for(int j=0; j<g[i].size(); j++)
if(c[i][g[i][j]]<=w)
gt[i].pb(g[i][j]);
vi prv(n,-1),deg(n);
vector<bool>vis(n);
ans=0;
dfs(gt,vis,x,-1);
if(!vis[y])return 0;
return ans;
}
int getMinimumFuelCapacity(int X, int Y){
ll l=1,r=1e9,ans=-1;
while(l<=r){
ll m=(l+r)/2;
if(ok(X,Y,m))
ans=m,r=m-1;
else
l=m+1;
}
return ans;
}
