#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
class dsu
{
public:
vector<int> p, s, ok; // ok - je tento komponent cyklus alebo obsahuje rozvetvenie?
int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
void merge(int a, int b)
{
a = root(a), b = root(b);
if (a == b) return ok[a] = true, void(); // cyklus
if (s[a] < s[b]) swap(a, b);
p[b] = a; s[a] += s[b];
ok[a] |= ok[b];
}
void good(int u) { ok[root(u)] = true; }
dsu(int n): p(vector<int>(n)), s(vector<int>(n, 1)), ok(vector<int>(n, false))
{
for (int i =0;i<n;i++) p[i] = i;
}
};
struct edge { int u, v, w; };
bool cmp(edge a, edge b) { return a.w < b.w; }
int n, m;
vector<edge> e;
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++) e.push_back({U[i], V[i], W[i]});
sort(e.begin(), e.end(), cmp);
}
int getMinimumFuelCapacity(int x, int y) {
dsu c(n);
vector<int> deg(n, 0);
for (int i = 0; i < m; i++)
{
c.merge(e[i].u, e[i].v);
deg[e[i].u]++, deg[e[i].v]++;
if (deg[e[i].u] >= 3) c.good(e[i].u);
if (deg[e[i].v] >= 3) c.good(e[i].v);
if (c.root(x) == c.root(y) && c.ok[c.root(x)]) return e[i].w;
}
return -1;
}
