#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int M = 200005;
int n, m;
array<int, 3> edges[M];
int fa[N+M], par[N+M];
bool isLine[N+M];
int e1[N+M], e2[N+M], weight[N+M];
int cur_id;
vector<int> adj[N+M];
int up[N+M][20], tin[N+M], tout[N+M], timer = -1;
int find(int v){
return v==fa[v]?v:fa[v]=find(fa[v]);
}
int unite(int u, int v){
int _u = u, _v = v;
u = find(u), v = find(v);
if(u == v){
if(!isLine[u]) return -1;
isLine[u] = 0;
e1[u] = e2[u] = -1;
return u;
}
fa[u] = fa[v] = par[u] = par[v] = cur_id++;
if(!isLine[u] || !isLine[v]) return cur_id-1;
for(int i = 0; i<2; i++){
if(e1[u] == _u && e1[v] == _v) e1[fa[u]] = e2[u], e2[fa[u]] = e2[v];
else if(e1[u] == _u && e2[v] == _v) e1[fa[u]] = e2[u], e2[fa[u]] = e1[v];
else if(e2[u] == _u && e1[v] == _v) e1[fa[u]] = e1[u], e2[fa[u]] = e2[v];
else if(e2[u] == _u && e2[v] == _v) e1[fa[u]] = e1[u], e2[fa[u]] = e1[v];
swap(_u, _v);
}
if(e1[fa[u]] == -1) return cur_id-1;
isLine[fa[u]] = 1;
// if(_u == 3 && _v == 1) cout << isLine[6] << endl;
return cur_id-1;
}
void dfs(int v){
tin[v] = ++timer;
up[v][0] = par[v];
for(int i = 1; i<20; i++)
up[v][i] = up[up[v][i-1]][i-1];
for(auto u : adj[v])
dfs(u);
tout[v] = timer;
}
bool isPar(int u, int v){
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int LCA(int u, int v){
if(isPar(u, v)) return u;
if(isPar(v, u)) return v;
for(int i = 19; i>=0; i--)
if(!isPar(up[u][i], v)) u = up[u][i];
return up[u][0];
}
int query(int v){
if(!isLine[v]) return weight[v];
for(int i = 19; i>=0; i--)
if(isLine[up[v][i]]) v = up[v][i];
v = up[v][0];
if(isLine[v]) return -1;
return weight[v];
}
void init(int _n, int _m, vector<int> U, vector<int> V, vector<int> W){
n = _n, m = _m;
for(int i = 0; i<m; i++)
edges[i] = {W[i], V[i], U[i]};
sort(edges, edges+m);
for(int i = 0; i<n+m; i++) fa[i] = i, e1[i] = e2[i] = -1, par[i] = i;
for(int i = 0; i<n; i++) isLine[i] = 1, e1[i] = e2[i] = i;
cur_id = n;
for(int i = 0; i<m; i++){
int v = unite(edges[i][1], edges[i][2]);
if(v==-1) continue;
weight[v] = edges[i][0];
}
// cout << cur_id << endl;
for(int i = 0; i<cur_id-1; i++)
adj[par[i]].push_back(i);
dfs(cur_id-1);
// cout << weight[7] << endl;
}
int getMinimumFuelCapacity(int u, int v){
return query(LCA(u, v));
}
