///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<long long, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, q, nn, m;
long long p[N], b[N], check[N], nxt[25][N], h[N];
vector<long long> adj[N];
struct edge{
long long u, v, w;
} e[N];
bool cmp(edge a, edge b){
return a.w < b.w;
}
long long Find(long long u){
if(u == p[u]) return u;
return p[u] = Find(p[u]);
}
void Union(long long u, long long v){
++b[u]; ++b[v];
long long uu = u, vv = v;
++n;
p[n] = n;
u = Find(u); v = Find(v);
if(u == v){
p[u] = n;
adj[u].pb(n);
adj[n].pb(u);
check[n] = 1;
// cout << uu << " " << vv << " " << n << " " << Find(4) << " " << Find(5) << "\n";
}else{
p[u] = n; p[v] = n;
check[n] = (check[u] || check[v] || b[uu] > 2 || b[vv] > 2);
adj[u].pb(n);
adj[n].pb(u);
adj[v].pb(n);
adj[n].pb(v);
// cout << uu << " " << vv << " " << n << " " << Find(4) << " " << Find(5) << "\n";
}
}
void dfs(long long u){
// cout << u << " " << h[u] << " " << nxt[0][u] << "\n";
for(long long v : adj[u]){
if(v == nxt[0][u]) continue;
h[v] = h[u] + 1;
nxt[0][v] = u;
dfs(v);
}
}
long long lca(long long u, long long v){
if(h[u] < h[v]) swap(u, v);
REP(k, 20, 0){
long long pu = nxt[k][u];
// cout << k << " " << u << " " << pu << "\n";
// cout << u << " " << v << " " << h[u] << " " << h[v] << "\n";
if(h[pu] >= h[v]){
u = pu;
}
}
if(u == v) return u;
REP(k, 20, 0){
long long pu = nxt[k][u], pv = nxt[k][v];
if(pu != pv){
u = pu; v = pv;
}
}
return nxt[0][u];
}
long long lift(long long u, long long mid){
REP(k, 20, 0){
if((1 << k) <= mid){
u = nxt[k][u];
mid -= (1 << k);
}
}
return u;
}
int getMinimumFuelCapacity(int u, int v){
long long p = lca(u, v);
long long l = 0, r = h[p];
// cout << lca << "\n";
while(l <= r){
long long mid = (l + r) / 2;
if(check[lift(p, mid)]) r = mid - 1;
else l = mid + 1;
}
if(l > h[p]) return -1;
return e[lift(p, l) - nn].w;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W){
n = N; m = M;
nn = N;
FOR(i, 1, m){
e[i] = {U[i - 1], V[i - 1], W[i - 1]};
}
sort(e + 1, e + 1 + m, cmp);
FOR(u, 0, n) p[u] = u;
FOR(i, 1, m){
long long u = e[i].u, v = e[i].v;
Union(u, v);
}
FOR(k, 0, 20){
FOR(u, 0, n + 1){
nxt[k][u] = n + 1;
}
}
h[n] = 1;
dfs(n);
FOR(k, 1, 20){
FOR(u, 0, n){
nxt[k][u] = nxt[k - 1][nxt[k - 1][u]];
}
}
}
//int main(){
// inp("in.txt");
////// out("out.txt");
// cin >> n >> m;
// nn = n;
// FOR(i, 1, m){
// int u, v, w; cin >> u >> v >> w;
// e[i] = {u, v, w};
// }
// sort(e + 1, e + 1 + m, cmp);
// FOR(u, 0, n) p[u] = u;
// FOR(i, 1, m){
// long long u = e[i].u, v = e[i].v;
//
// Union(u, v);
// }
//
// FOR(k, 0, 20){
// FOR(u, 0, n + 1){
// nxt[k][u] = n + 1;
// }
// }
//
// h[n] = 1;
// dfs(n);
// FOR(k, 1, 20){
// FOR(u, 0, n){
// nxt[k][u] = nxt[k - 1][nxt[k - 1][u]];
// }
// }
//// cout << nxt[2][nxt[2][4]] << '\n';
//
// cin >> q;
// while(q--){
// int u, v; cin >> u >> v;
// cout << getMinimumFuelCapacity(u, v) << "\n";
// }
//}
