#include "swap.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <assert.h>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppi pair<pii, int>
#define vi vector<int>
using namespace std;
const int INF = 1e9, LG = 19;
ppi edge[200001];
int par[100001], cur[100001], idx, deg[100001];
vi tree[300001];
int sps[300001][LG], val[300001], h[300001];
bool st[300001];
inline bool comp(const ppi &l, const ppi &r)
{
return make_pair(l.snd, l.fst) < make_pair(r.snd, r.fst);
}
int fn(int x) {return par[x] = (par[x] == x) ? x : fn(par[x]);}
void jn(int a, int b, int v)
{
deg[a]++; deg[b]++;
bool ck = (deg[a] > 2) || (deg[b] > 2);
a = fn(a), b = fn(b);
if (a != b)
{
ck |= st[cur[a]] || st[cur[b]];
par[b] = a;
//cout << "Edge from " << idx << " -> " << cur[a] << "\n";
//cout << "Edge from " << idx << " -> " << cur[b] << "\n";
tree[idx].push_back(cur[a]);
tree[idx].push_back(cur[b]);
cur[a] = idx++;
val[cur[a]] = v; st[cur[a]] = ck;
//cout << "Data : " << cur[a] << " " << val[cur[a]] << " " << st[cur[a]] << "\n";
}
else
{
if (!st[cur[a]])
{
//cout << "Edge from " << idx << " -> " << cur[a] << "\n";
tree[idx].push_back(cur[a]);
cur[a] = idx++;
val[cur[a]] = v; st[cur[a]] = 1;
//cout << "Data : " << cur[a] << " " << val[cur[a]] << " " << st[cur[a]] << "\n";
}
}
}
void DFS(int u, int p)
{
h[u] = (p == -1) ? 0 : (h[p] + 1);
sps[u][0] = p;
//cout << u << " " << h[u] << " " << sps[u][0] << "\n";
for (int i = 1; i < LG; i++)
{
if (sps[u][i - 1] != -1) {sps[u][i] = sps[sps[u][i - 1]][i - 1];}
else {sps[u][i] = -1;}
}
for (auto v : tree[u]) DFS(v, u);
}
int findLCA(int u, int v)
{
if (h[u] > h[v]) swap(u, v);
for (int i = 0; h[v] - h[u]; i++)
{
assert(i < LG);
if ((h[v] - h[u]) & (1 << i)) v = sps[v][i];
}
if (u == v) return u;
for (int i = LG - 1; i >= 0; i--)
{
if (sps[u][i] != sps[v][i])
{
u = sps[u][i];
v = sps[v][i];
}
}
return sps[u][0];
}
int findValid(int x)
{
if (st[x]) return x;
for (int i = LG - 1; i >= 0; i--)
{
if (sps[x][i] != -1 && !st[sps[x][i]]) {x = sps[x][i];}
}
return sps[x][0];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
for (int i = 0; i < N; i++)
{
cur[i] = i; deg[i] = 0; par[i] = i;
}
idx = N;
for (int i = 0; i < M; i++)
{
edge[i] = {{U[i], V[i]}, W[i]};
}
sort(edge, edge + M, comp);
for (int i = 0; i < M; i++)
{
jn(edge[i].fst.fst, edge[i].fst.snd, edge[i].snd);
}
DFS(idx - 1, -1);
}
int getMinimumFuelCapacity(int X, int Y)
{
if (!st[idx - 1]) return -1;
else
{
int L = findLCA(X, Y);
return val[findValid(L)];
}
}
