#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define vec vector
#define ll long long
#define all(x) x.begin(), x.end()
int const inf = 1e9 + 1;
// let's rephrase the problem statement
// I will give you city i and city j, find a way that have a cycle, and the maximum gas is minimized
// first, find the MST, with this, we have a tree
// after that, we will look for cycles with minimum possible (we can find them on the go in MST algorithm)
// the idea is changed
// when it will be impossible and the answer is -1 for all the cities pairs ?
// when the graph is a path, then the answer is always -1
// otherwise, I can choose one of the following:
// 1 - an edge which isn't on the path from a and b, but on one of its vertices (excpet a and b)
// 2 - choose 2 edges in whether a or b such that none of them is on the path from a to b
// 3 - choose another path is it exists and take it, such that the start is connected with a and the end is connected with b
// let's try to implement this idea
// first, dsu to get time complexity O(alpha)
struct DSU
{
int n;
vec<int> par, sz;
DSU(int _n)
{
n = _n;
sz.assign(n, 1);
par.resize(n);
iota(all(par), 0);
}
int find(int u)
{
return par[u] = (par[u] == u ? u : find(par[u]));
}
bool same(int u, int v)
{
return find(u) == find(v);
}
bool unite(int u, int v)
{
u = find(u);
v = find(v);
if(u == v)
return false;
if(sz[u] > sz[v])
swap(u, v);
sz[v] += sz[u];
par[u] = v;
return true;
}
};
int n, m;
vec<int> u, v, w;
int mn = inf;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
n = N, m = M;
u = U, v = V, w = W;
// let's solve the first subtask
if(m > n - 1)
mn = *max_element(all(w));
// vec<tuple<int, int, int>> edges;
// for(int i = 0; i < m; i++)
// edges[i] = {w[i], u[i], v[i]};
// sort(all(edges));
// DSU dsu(n);
// // MST code
// for(auto [wi, ui, vi]: edges)
// {
// int x = dsu.find(ui);
// int y = dsu.find(vi);
// if(x != y)
// {
// dsu.unite(x, y);
// }
// }
}
int getMinimumFuelCapacity(int X, int Y)
{
int x = X, y = Y;
return (mn == inf ? -1 : mn);
}
/*
- SAMPLES -
01.in
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
01.out
3
10
4
02.in
3 2
0 1 5
0 2 5
1
1 2
02.out
-1
*/
