#include <bits/stdc++.h>

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops,inline,fast-math")
#pragma GCC target ("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
} in ("apm.in");

ofstream out ("apm.out");

const int maxcSize = 100002;
const int inf = 0x3f3f3f3f;

int parent[maxcSize], cSize[maxcSize];
int findParent(int node) {
    while (node != parent[node]) node = parent[node];
    return node;
}

bool connect(int nodeA, int nodeB) {
    nodeA = findParent( nodeA );
    nodeB = findParent( nodeB );

    if (nodeA == nodeB) return false;

    if (cSize[nodeA] < cSize[nodeB]) swap(nodeA, nodeB);
    cSize[nodeA] += cSize[nodeB]; parent[nodeB] = nodeA;
    return true;
}

struct type {int nodeA, nodeB, cost;};

bool cmpFunction(type a, type b) {
    if (a.cost == b.cost) {
        if (a.nodeA == b.nodeA) return a.nodeB < b.nodeB;
        return a.nodeA < b.nodeA;
    }
    return a.cost < b.cost;
}
vector <type> edges;
vector <pair <int , int>> toShow;
int main( ) {
    int numNodes, numEdges; in >> numNodes >> numEdges;

    type curr; edges.reserve(numEdges + 1);
    for (int i = 0; i < numEdges; ++i) {
        in >> curr.nodeA >> curr.nodeB >> curr.cost;
        edges.emplace_back(curr);
    }
    sort(edges.begin( ), edges.end( ), cmpFunction);

    for (int i = 1; i <= numNodes; ++i) {
        parent[i] = i; cSize[i] = 1;
    }

    int ans = 0; toShow.reserve(numNodes);
    for (auto edge : edges) {
        if (toShow.size( ) == numNodes - 1) break;
        if (connect(edge.nodeA, edge.nodeB)) {
            toShow.emplace_back(edge.nodeA, edge.nodeB);
            ans += edge.cost;
        }
    }

    out << ans << '\n';
    out << toShow.size( ) << '\n';
    for (auto edge : toShow) out << edge.first << ' ' << edge.second << '\n';
    return 0;
}