#include <bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 1e6 + 5;
const int LG = 21;
int n,m,node,dsu[maxN],val[maxN],deg[maxN];
int up[LG][maxN],lg[maxN],res[maxN],dep[maxN];
bool swp[maxN];
vector<int> adj[maxN];
struct Tedge
{
int x,y,w;
}
e[maxN];
int findset(int u)
{
return dsu[u] == u ? u : dsu[u] = findset(dsu[u]);
}
void add(int u,int v,int w)
{
int v1 = v,u1 = u;
deg[u]++;deg[v]++;
++node;
u = findset(u);v = findset(v);
dsu[u] = dsu[v] = node;
dsu[node] = node;
val[node] = w;
adj[node].push_back(u);
if (u != v) adj[node].push_back(v);
if (u == v || swp[u] || swp[v] || deg[u1] > 2 || deg[v1] > 2) swp[node] = true;
else swp[node] = false;
}
bool cmp(const Tedge& a,const Tedge& b)
{
return a.w < b.w;
}
void dfs(int u,int par)
{
if (swp[u]) res[u] = val[u];
else res[u] = res[par];
up[0][u] = par;
for (int v : adj[u])
{
dep[v] = dep[u] + 1;
dfs(v,u);
}
}
void presolve()
{
lg[1] = 0;
for (int i = 2;i <= node;++i) lg[i] = lg[i / 2] + 1;
for (int j = 1;j < LG;++j)
for (int i = 1;i <= node;++i)
up[j][i] = up[j - 1][up[j - 1][i]];
}
int lca(int u,int v)
{
int u1 = u,v1 = v;
if (dep[u] < dep[v]) swap(u,v);
int k = dep[u] - dep[v];
for (int i = lg[k];i >= 0;--i)
if (k & (1 << i)) u = up[i][u];
if (u == v) return u;
k = dep[u];
for (int i = lg[k];i >= 0;--i)
{
if (up[i][u] != up[i][v])
{
u = up[i][u];
v = up[i][v];
}
}
return up[0][u];
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W)
{
n = N;m = M;
node = n;
for (int i = 1;i <= M;++i)
{
e[i].x = U[i - 1] + 1;
e[i].y = V[i - 1] + 1;
e[i].w = W[i - 1];
}
sort(e + 1,e + m + 1,cmp);
for (int i = 1;i <= n;++i)
{
dsu[i] = i;
if (deg[i] >= 3) swp[i] = true;
else swp[i] = false;
}
for (int i = 1;i <= m;++i)
{
//cout << e[i].x << " " << e[i].y << " " << e[i].w << "\n";
add(e[i].x,e[i].y,e[i].w);
}
//cout << "A\n";
//for (int i = 1;i <= node;++i) for (int v : adj[i]) cout << i << " " << v << "\n";
res[0] = -1;dep[node] = 0;
dfs(node,0);
presolve();
}
int getMinimumFuelCapacity(int X, int Y)
{
++X,++Y;
//cout << X << " " << Y << " " << swp[lca(X,Y)] << " ";
return res[lca(X,Y)];
}
