#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

using pii = pair<int, int>;

const int N = 2e5 + 5, LG = 1;


struct Edge {
	int link, cost; };

vector<Edge> g[N];
int dist[N], lvl[N], far[LG][N], mxm[LG][N];
bool in_tree[N];

int n, m, q, sum;


static void prim() {
	priority_queue<pii> pq;
	pii top;
	int cost, u;

	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	in_tree[1] = 1;
	pq.push({0, 1});
	
	while (!pq.empty()) {
		u = pq.top().y, cost = -pq.top().x, pq.pop();
		if (cost != dist[u])
			continue;
		in_tree[u] = true;

		for (auto v: g[u]) if (!in_tree[v.link] && dist[v.link] > v.cost) {
			dist[v.link] = v.cost;
			lvl[v.link] = lvl[u] + 1;
			far[0][v.link] = u;
			mxm[0][v.link] = v.cost;
			pq.push({-v.cost, v.link}); } } }

static void initialize() {
	for (int lg = 1; lg < LG; ++lg)
	for (int i = 1; i <= n; ++i) {
		far[lg][i] = far[lg - 1][far[lg - 1][i]];
		mxm[lg][i] = max(mxm[lg - 1][i], mxm[lg - 1][far[lg - 1][i]]); } }

static int query(int u, int v) {
	int ant = -1e9;
	if (lvl[u] < lvl[v])
		swap(u, v);

	for (int lg = LG - 1; lg >= 0; --lg)
		if ((lvl[u] - lvl[v]) & (1 << lg)) {
			ant = max(ant, mxm[lg][u]);
			u = far[lg][u]; }
	if (u == v)
		return ant - 1;
	for (int lg = LG - 1; lg >= 0; --lg)
		if (far[lg][u] != far[lg][v]) {
			ant = max(ant, mxm[lg][u]);
			ant = max(ant, mxm[lg][u]);
			u = far[lg][u], v = far[lg][v]; }
	ant = max(ant, mxm[0][u]);
	ant = max(ant, mxm[0][v]);
	return ant - 1; }

int main() {
	fi >> n >> m;
	for (int u, v, c, i = 0; i < m; ++i) {
		fi >> u >> v >> c;
		g[u].push_back({v, c});
		g[v].push_back({u, c}); }

	prim();
	for (int i = 1; i <= n; ++i)
		sum+= dist[i];
	fo << sum << '\n' << n - 1 << '\n';
	for (int i = 2; i <= n; ++i)
		fo << i << ' ' << far[0][i] << '\n';

	for (int u, v, i = 0; i < q; ++i) {
		fi >> u >> v;
		fo << query(u, v) << '\n'; }

	return 0; }