#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;
typedef double lf;

using namespace std;

const int MAXN = 2e5 + 10;

int n, m;
struct Edge
{
    int u, v, w;
    bool operator < (const Edge x) const {return w < x.w;}
}e[MAXN];

int g[MAXN][2];

int fa[MAXN], hd[MAXN], tl[MAXN], tag[MAXN], tot;
int Find(int k) {return k == fa[k] ? k : fa[k] = Find(fa[k]);}

int lg[MAXN], f[MAXN][23], dep[MAXN];
void DFS(int u, int t)
{
    dep[u] = dep[t] + 1, f[u][0] = t;
    for (int i = 1; i < lg[dep[u]]; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    if (u <= n) return;
    for (int c = 0; c < 2; c++)
    {
        if (!tag[g[u][c]]) tag[g[u][c]] = tag[u];
        DFS(g[u][c], u);
    }
}

void init(int N, int M, vector <int> U, vector <int> V, vector <int> W)
{
    n = N, m = M;
    for (int i = 1; i <= m; i++) e[i].u = U[i - 1] + 1, e[i].v = V[i - 1] + 1, e[i].w = W[i - 1];
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; i++) fa[i] = hd[i] = tl[i] = i, tag[i] = 0;
    tot = n;
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].u, v = e[i].v;
        if (Find(u) == Find(v))
        {
            int rt = Find(u);
            if (!tag[rt]) tag[rt] = i;
        }
        else
        {
            u = Find(u), v = Find(v);
            tot++, fa[tot] = tot, g[tot][0] = u, g[tot][1] = v;
            fa[u] = fa[v] = tot;
            if (tag[u] || tag[v]) tag[tot] = i;
            else if (!(e[i].u == hd[u] || e[i].u == tl[u]) || !(e[i].v == hd[v] || e[i].v == tl[v])) tag[tot] = i;
            else
            {
                hd[tot] = (e[i].u == hd[u] ? tl[u] : hd[u]), tl[tot] = (e[i].v == hd[v] ? tl[v] : hd[v]);
                tag[tot] = 0;
            }
        }
    }
    for (int i = 1; i <= tot; i++) lg[i] = lg[i >> 1] + 1;
    DFS(tot, 0);
}

int getMinimumFuelCapacity(int x, int y)
{
    x++, y++;
    int lca = tot;
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) lca = x;
    else
    {
        for (int i = lg[dep[x]] - 1; ~i; i--)
            if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
        lca = f[x][0];
    }
    if (tag[lca]) return e[tag[lca]].w;
    return -1;
}