#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,M=2e5+50,S=600,inf=1e9+50;
void chmx(int &x,int y){x=max(x,y);}
mt19937 rng(time(0));
vector<pair<int,int>>E[N];
int n,m;
vector<array<int,3>>edges;
/*struct DSU{
vector<array<int,5>>undo;
int par[N],sajz[N],deg[N],ciklus[N];
DSU(){for(int i=0;i<N;i++)par[i]=i,sajz[i]=1,deg[i]=0;}
int FS(int u){if(par[u]==u)return u;return FS(par[u]);}
void US(int u,int v){
deg[u]++,deg[v]++;
int U=FS(u),V=FS(v);
if(deg[u]>2) ciklus[U]++;
if(deg[v]>2) ciklus[V]++;
int swp=0;
if(U==V) ciklus[U]++;
else{
if(sajz[U]<sajz[V]) swap(U,V),swp=1;
par[V]=U;
sajz[U]+=sajz[V];
ciklus[U]+=ciklus[V];
if(swp==1) swap(U,V);
}
undo.pb({u,v,U,V,swp});
}
void Undo(){
auto [u,v,U,V,swp]=undo.back();undo.pop_back();
if(U==V) ciklus[U]--;
else{
if(swp) swap(U,V);
ciklus[U]-=ciklus[V];
sajz[U]-=sajz[V];
par[V]=V;
if(swp) swap(U,V);
}
if(deg[u]>2) ciklus[U]--;
if(deg[v]>2) ciklus[V]--;
deg[u]--,deg[v]--;
}
}dsu[M/S+1];*/
/*struct DSU{
int par[N+M],deg[N+M],ciklus[N+M],sajz[N+M],tajm[N+M],tm,nc=N;
DSU(){for(int i=0;i<N+M;i++)par[i]=i,sajz[i]=1;}
void Copy(int u){
++nc;
tajm[nc]=tm;
par[u]=nc;
sajz[nc]=sajz[u]+1;
ciklus[nc]=ciklus[u];
}
int FS(int u,int t){if(tajm[par[u]]>t||par[u]==u)return u;return FS(par[u],t);}
int Ciklus(int u,int t){if(tajm[par[u]]>t||par[u]==u)return ciklus[u];return max(ciklus[u],Ciklus(par[u],t));}
void US(int u,int v){
deg[u]++,deg[v]++;
int U=FS(u,tm),V=FS(v,tm);
//printf("%i %i %i %i\n",u,v,U,V);
tm++;
if(U==V){
//printf("DA\n");
if(ciklus[U]==0){
//printf("DA\n");
Copy(U);
ciklus[nc]++;
}
return;
}
if(ciklus[U]==0&°[u]>=3){
Copy(U);
ciklus[nc]++;
U=nc;
}
if(ciklus[V]==0&°[v]>=3){
Copy(V);
ciklus[nc]++;
V=nc;
}
if(rng()%2) swap(U,V);
Copy(V);V=nc;
par[V]=U;
//sajz[U]+=sajz[V];
//ciklus[U]+=ciklus[V];
}
}dsu;*/
struct DSU{
int par[N],maks[N],deg[N],ciklus[N];
DSU(){for(int i=0;i<N;i++) par[i]=i;}
int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);}
void US(int u,int v,int w){
deg[u]++,deg[v]++;
int x=deg[u],y=deg[v];
u=FS(u),v=FS(v);
if(x==3) ciklus[u]++;
if(y==3) ciklus[v]++;
if(u==v){chmx(maks[u],w);ciklus[u]++;return;}
par[u]=v;
chmx(maks[v],maks[u]);
ciklus[v]+=ciklus[u];
}
}dsu;
int ANS[N];
void init(int n1,int m1,vector<int>U,vector<int>V,vector<int>W) {
n=n1,m=m1;
for(int i=0;i<m;i++){
E[U[i]].pb({V[i],W[i]});
E[V[i]].pb({U[i],W[i]});
edges.pb({W[i],U[i],V[i]});
}
sort(edges.begin(),edges.end());
vector<int>vtx;
bool was[n+10]={0};was[0]=true;
for(int i=0;i<n;i++) ANS[i]=-1;
for(auto [w,u,v]:edges){
dsu.US(u,v,w);
if(!was[u]&&dsu.FS(u)==dsu.FS(0)) vtx.pb(u),was[u]=true;
if(!was[v]&&dsu.FS(v)==dsu.FS(0)) vtx.pb(v),was[v]=true;
if(dsu.ciklus[dsu.FS(0)]>0){
for(auto i:vtx) ANS[i]=w;
vtx.clear();
}
}
/*for(int i=0;i<m;i++){
//printf("%i\n",i);
dsu.US(edges[i][1],edges[i][2]);
}/*
//printf("da\n");
/*for(int B=0;B*S-S<=m;B++){
for(int i=0;i<min(m,B*S);i++){
dsu[B].US(edges[i][1],edges[i][2]);
}
}*/
/*for(int i=0;i<n;i++){
sort(E[i].begin(),E[i].end(),[&](pair<int,int>a,pair<int,int>b){return a.se<b.se;});
if(E[i].size()<3) Val[i]=inf+100;
else Val[i]=E[i][2].se;
}*/
}
/*bool was[N],ciklus;
int par[N],deg[N];
void DFS(int u,int mid,int p=-1){
was[u]=true;
for(auto [v,w]:E[u]){
if(w>mid) continue;
if(was[v]&&v!=p) ciklus=true;
if(!was[v]){
par[v]=u;
deg[u]++,deg[v]++;
DFS(v,mid,u);
}
}
}*/
int getMinimumFuelCapacity(int X,int Y){
return ANS[Y];
/*if(dsu.FS(X)!=dsu.FS(Y)) return -1;
if(dsu.ciklus[dsu.FS(X)]==0) return -1;
return dsu.maks[dsu.FS(X)];*/
/*int l=1,r=m,res=-1;
while(l<=r){
int mid=l+r>>1;
int rootX=dsu.FS(X,mid),rootY=dsu.FS(Y,mid);
if(rootX==rootY&&dsu.Ciklus(X,mid)>0){res=edges[mid-1][0],r=mid-1;}
else l=mid+1;
}
return res;*/
/*int ind=0;
for(int B=0;B*S-S<=m;B++){
int rootX=dsu[B].FS(X),rootY=dsu[B].FS(Y);
if(rootX==rootY){
if(dsu[B].ciklus[rootX]>0) break;
}
ind=B;
}
//printf("%i\n",ind);
int res=-1,cnt=0;
for(int B=ind,i=B*S;i<m;i++){
//printf("%i %i %i\n",edges[i][0],edges[i][1],edges[i][2]);
dsu[B].US(edges[i][1],edges[i][2]);
cnt++;
int rootX=dsu[B].FS(X),rootY=dsu[B].FS(Y);
if(rootX==rootY){
//printf("da\n");
if(dsu[B].ciklus[rootX]>0) res=edges[i][0];
}
if(res>-1) break;
}
while(cnt--) dsu[ind].Undo();
return res;*/
/*int l=0,r=inf,res=-1;
while(l<=r){
int mid=l+r>>1;
for(int i=0;i<=n;i++) was[i]=false,par[i]=deg[i]=0;ciklus=false;
DFS(X,mid);
if(!was[Y]){l=mid+1;continue;}
if(ciklus){res=mid;r=mid-1;continue;}
int mn=inf+1000;
bool moze=false;
for(int i=0;i<n;i++) if(deg[i]>2) moze=true;
if(moze){res=mid;r=mid-1;}
else l=mid+1;
}
return res;*/
}
