#include <fstream>
#include <vector>
#include <algorithm>

#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) {
    return a.cost < b.cost;
}

type edges[4 * maxcSize];
vector <pair <int , int>> toShow;
int main( ) {
    int numNodes, numEdges; in >> numNodes >> numEdges;

    for (int i = 0; i < numEdges; ++i) {
        in >> edges[i].nodeA >> edges[i].nodeB >> edges[i].cost;
    }
    sort(edges, edges + numEdges, cmpFunction);

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

    int ans = 0; toShow.reserve(numNodes);
    for (int i = 0; i < numEdges; ++i) {
        if (toShow.size( ) == numNodes - 1) break;
        if (connect(edges[i].nodeA, edges[i].nodeB)) {
            toShow.emplace_back(edges[i].nodeA, edges[i].nodeB);
            ans += edges[i].cost;
        }
    }

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