#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
const int mxN=1e5, mxM=2e5;
int n, m, p[2*mxN], anc[2*mxN][18], first[2*mxN], n2, d[2*mxN], ew[2*mxN], epa[2*mxN], epb[2*mxN];
ar<int, 3> e[mxM];
vector<int> adj[2*mxN];
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
void dfs(int u) {
for (int v : adj[u]) {
d[v]=d[u]+1;
if (ew[u]!=-1&&(ew[v]==-1||ew[u]<ew[v]))
ew[v]=ew[u];
dfs(v);
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N, m=M, n2=n;
for (int i=0; i<m; ++i)
e[i]={W[i], U[i], V[i]};
sort(e, e+m);
iota(p, p+2*n, 0);
memset(anc, -1, sizeof(anc));
memset(first, -1, sizeof(first));
for (int i=0; i<n; ++i)
epa[i]=epb[i]=i;
for (int i=0; i<m; ++i) {
int u=find(e[i][1]), v=find(e[i][2]);
if (u!=v) {
p[u]=p[v]=anc[u][0]=anc[v][0]=n2;
first[n2]=first[v]==-1||first[u]!=-1&&first[u]<first[v]?first[u]:first[v];
if (first[n2]==-1) {
if (epa[u]!=e[i][1]&&epb[u]!=e[i][1]||epa[v]!=e[i][2]&&epb[v]!=e[i][2])
first[n2]=e[i][0];
else {
epa[n2]=epa[u]^epb[u]^e[i][1];
epb[n2]=epa[v]^epb[v]^e[i][2];
//cout << epa[u] << " " << epb[u] << " " << epa[v] << " " << epb[v] << " " << e[i][1] << " " << e[i][2] << " " << epa[n2] << " " << epb[n2] << endl;
}
}
ew[n2]=e[i][0];
adj[n2].push_back(u);
adj[n2].push_back(v);
++n2;
} else if (first[u]==-1)
first[u]=e[i][0];
}
assert(n2==2*n-1);
for (int j=1; j<18; ++j)
for (int i=0; i<n2; ++i)
anc[i][j]=anc[i][j-1]^-1?anc[anc[i][j-1]][j-1]:-1;
//for (int i=0; i<n2; ++i)
// cout << epa[i] << " " << epb[i] << " " << first[i] << endl;
for (int i=n; i<n2; ++i) {
ew[i]=first[i]^-1?max(ew[i], first[i]):-1;
//cout << i << " " << ew[i] << endl;
}
dfs(n2-1);
//for (int i=n; i<n2; ++i)
// cout << i << " " << ew[i] << endl;
}
int lca(int u, int v) {
if (d[u]>d[v])
swap(u, v);
for (int i=17; ~i; --i)
if (d[v]-(1<<i)>=d[u])
v=anc[v][i];
if (u==v)
return u;
for (int i=17; ~i; --i)
if (anc[u][i]!=anc[v][i])
u=anc[u][i], v=anc[v][i];
return anc[u][0];
}
int getMinimumFuelCapacity(int u, int v) {
return ew[lca(u, v)];
}
