#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int INF = 1e9+5;
const int lg = 18;
int n, m;
int Wmax;
int sp[lg][maxn];
int sp_mx[lg][maxn], sp_mn[lg][maxn];
int dep[maxn];
int in_tree[maxn];
vector<pair<int, int>> g[maxn];
vector<pair<int, pair<int, int>>> E;
int up[maxn];
int Find(int x){
return up[x] != -1 ? up[x] = Find(up[x]) : x;
}
bool Union(int a, int b){
a = Find(a);
b = Find(b);
if(a == b)return false;
up[a] = b;
return true;
}
void dfs(int x, int p){
sp_mn[0][x] = INF;
sp[0][x] = p;
for(auto v: g[x]){
if(v.first == p)continue;
dep[v.first] = dep[x] + 1;
sp_mx[0][v.first] = v.second;
dfs(v.first, x);
}
}
void build(){
for(int i = 1; i < lg; i++){
for(int j = 0; j < n; j++){
if(sp[i-1][j] == -1)sp[i][j] = -1;
else {
sp[i][j] = sp[i-1][sp[i-1][j]];
sp_mx[i][j] = max(sp_mx[i-1][j], sp_mx[i-1][sp[i-1][j]]);
}
sp_mn[i][j] = INF;
}
}
}
void tup_upd(int &x, int dist, int w){
for(int i = 0; i < lg; i++){
if(dist&(1<<i)){
sp_mn[i][x] = w;
x = sp[i][x];
}
}
}
void upd_path(int a, int b, int w){
if(dep[a] < dep[b])swap(a, b);
tup_upd(a, dep[a] - dep[b], w);
if(a == b)return;
for(int i = lg-1; i >= 0; i--){
if(sp[i][a] != sp[i][b]){
sp_mn[i][a] = min(sp_mn[i][a], w);
sp_mn[i][b] = min(sp_mn[i][b], w);
a = sp[i][a];
b = sp[i][b];
}
}
sp_mn[0][a] = min(sp_mn[0][a], w);
sp_mn[0][b] = min(sp_mn[0][b], w);
}
void push(){
for(int i = lg-1; i > 0; i--){
for(int j = 0; j < n; j++){
if(sp[i][j] == -1)continue;
sp_mn[i-1][j] = min(sp_mn[i-1][j], sp_mn[i][j]);
sp_mn[i-1][sp[i-1][j]] = min(sp_mn[i-1][sp[i-1][j]], sp_mn[i][j]);
}
}
}
void tup_query(int &x, int dist, int &mx, int &mn){
for(int i = 0; i < lg; i++){
if(dist&(1<<i)){
mn = min(sp_mn[i][x], mn);
mx = max(sp_mx[i][x], mx);
x = sp[i][x];
}
}
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
m = M;
Wmax = *max_element(W.begin(), W.end());
}
int getMinimumFuelCapacity(int a, int b) {
if(n == m)return Wmax;
return -1;
}
