#include <bits/stdc++.h>
#include "swap.h"
#define DIM 200010
#define INF 2000000000
using namespace std;
struct muchie{
int x,y,cost;
} mch[DIM];
vector<pair <int,int> > L[DIM];
int t[DIM],ok[DIM],g[DIM];
int n,m,subtask,maxi;
inline int cmp (muchie a, muchie b){
return a.cost < b.cost;
}
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++){
int x = U[i], y = V[i], cost = W[i];
x++, y++;
L[x].push_back(make_pair(y,cost));
L[y].push_back(make_pair(x,cost));
maxi = max (maxi,cost);
mch[i+1] = {x,y,cost};
}
subtask = 1;
for (int i=1;i<=n;i++)
if (L[i].size() > 2)
subtask = 0;
sort (mch+1,mch+m+1,cmp);
}
inline int get_rad (int x){
while (t[x] > 0)
x = t[x];
return x;
}
int getMinimumFuelCapacity(int X, int Y) {
if (subtask == 1){
if (m == n-1)
return -1;
else return maxi;
}
X++, Y++;
for (int i=1;i<=n;i++){
t[i] = -1;
ok[i] = g[i] = 0;
}
for (int i=1;i<=m;i++){
int x = mch[i].x, y = mch[i].y;
int radx = get_rad(x), rady = get_rad(y);
if (radx != rady){
if (t[radx] > t[rady])
swap (radx, rady);
ok[radx] |= ok[rady];
t[radx] += t[rady];
t[rady] = radx;
g[x]++, g[y]++;
if (g[x] >= 3 || g[y] >= 3)
ok[radx] = 1;
} else {
/// o sa am un ciclu in componenta asta
ok[radx] = 1;
}
if (get_rad(X) == get_rad(Y) && ok[get_rad(X)])
return mch[i].cost;
}
return -1;
}
/*
int main (){
FILE *fin = fopen ("date.in", "r");
FILE *fout = fopen ("date.out", "w");
int N, M;
assert(2 == fscanf(fin, "%d %d", &N, &M));
std::vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == fscanf(fin, "%d %d %d", &U[i], &V[i], &W[i]));
}
int Q;
assert(1 == fscanf(fin,"%d", &Q));
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
assert(2 == fscanf(fin,"%d %d", &X[i], &Y[i]));
}
init(N, M, U, V, W);
std::vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i) {
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i) {
fprintf(fout, "%d\n", minimum_fuel_capacities[i]);
}
return 0;
}
*/
