#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAXN 100000
#define QWQ cout << "QWQ" << endl;
using namespace std;
struct node {
	int to, val;
	node(int T, int V) {
		to = T, val = V;
	}
};
vector <node> gra[MAXN + 10];
int n, m;
struct Edge {
	int x, y, z;
} edge[MAXN + 10];
int fa[MAXN + 10];
int Find(int x) {
	if(x == fa[x]) return x;
	else return fa[x] = Find(fa[x]);
}
bool cmp(Edge x, Edge y) {
	return x.z > y.z;
} 
void kruskal() {
	for(int p = 1; p <= n; p++) fa[p] = p;
	sort(edge + 1, edge + m + 1, cmp);
	int cnt = 0;
	for(int p = 1; p <= m; p++) {
		int U = Find(edge[p].x), V = Find(edge[p].y);
		if(U == V) continue;
		fa[V] = U;
		gra[edge[p].x].push_back(node(edge[p].y, edge[p].z));
		gra[edge[p].y].push_back(node(edge[p].x, edge[p].z));
		cout << edge[p].x << ' ' << edge[p].y << ' ' << edge[p].z << endl;
	}
}

int jump[MAXN + 10][20], F[MAXN + 10][20], de[MAXN + 10];
void dfs(int u, int fa, int ue) {
	de[u] = de[fa] + 1;
	jump[u][0] = fa; F[u][0] = ue;
	for(int p = 1; p <= 20; p++) {
		jump[u][p] = jump[jump[u][p - 1]][p - 1];
		F[u][p] = min(F[u][p - 1], F[jump[u][p - 1]][p - 1]);
	}
	for(int p = 0; p < gra[u].size(); p++) {
		int v = gra[u][p].to, w = gra[u][p].val;
		if(v != fa) dfs(v, u, w);
	}
}
int get_lca(int x, int y) {
	if(Find(x) != Find(y)) return -1;
	int minn = 0x7f7f7f7f;
	if(de[x] < de[y]) swap(x, y);
	for(int p = 20; p >= 0; p--)
		if(de[jump[x][p]] >= de[y]) {
			cout << jump[x][p] << ' ' << x << ' ' << p << endl;
			minn = min(minn, F[x][p]), x = jump[x][p];
		}
	if(x == y) return minn;
	for(int p = 20; p >= 0; p--)
		if(jump[x][p] != jump[y][p]) {
			minn = min(minn, min(F[x][p], F[y][p])); 
			x = jump[x][p], y = jump[y][p];
		}
	minn = min(minn, min(F[x][0], F[y][0]));
	return minn;
} 
int main() {
	memset(F, 0x7f, sizeof(F));
	cin >> n >> m;
	for(int p = 1; p <= m; p++)
		cin >> edge[p].x >> edge[p].y >> edge[p].z;
	kruskal();
	//dfs(1, 0, 0x7f7f7f7f);
	for(int p = 1; p <= n; p++)
		if(!de[p]) dfs(p, 0, 0x7f7f7f7f);
	for(int p = 1; p <= n; p++)
		for(int i = 1; i <= 20; i++) {
		cout << p << ' ' << i << ' ' << jump[p][i] << endl;
		}
	cout << jump[3][20] << endl;
	int q; cin >> q;
	for(int p = 1, x, y; p <= q; p++) {
		cin >> x >> y;
		cout << get_lca(x, y) << endl;
	}
}

hack 是

5 7
4 3 4440
3 1 22348
1 3 28368
2 4 25086
5 3 6991
4 3 10638
3 1 11106
4
4 5
1 3
5 4
2 5

就是倍增预处理的 $2^k$ 级祖先中 $3$ 的 $2^{20}$ 祖先是 $3$/yun
这波不会了，感觉预处理貌似没啥问题/yun 希望大家忽略一下里面奇怪的 cout qwq

如果是傻逼问题的话请喷 SX 是傻逼 qAq