#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>

long N, M;
long parent[200001];
long rank[200001];

struct edge {
    long src;
    long dest;
    long weight;
};

bool compareByWeight (const edge &a, const edge &b) {
    return a.weight < b.weight;
}

void makeSet (long x) {
    parent[x] = x;
    rank[x] = 0;
}

long findSet(long x) {
    if (parent[x] != x) {
        parent[x] = findSet(parent[x]);
    }

    return parent[x];
}


void setUnion (long x, long y) {
    long xRoot = findSet(x);
    long yRoot = findSet(y);

    if (xRoot == yRoot) {
        return;
    }

    if (rank[xRoot] < rank[yRoot]) {
        parent[xRoot] = yRoot;
    }
    else if (rank[xRoot] > rank[yRoot]) {
        parent[yRoot] = xRoot;
    }
    else {
        parent[yRoot] = xRoot;
        rank[xRoot] = rank[xRoot] + 1;
    }
}

std::vector<edge> kruskal (const std::vector<edge> &edges, long &sum) {
    std::vector<edge> result;

    for (long i = 1; i <= N; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    std::vector<edge> sortedEdges(edges);

    std::sort(sortedEdges.begin(), sortedEdges.end(), compareByWeight);

    for (unsigned long i = 0; i < sortedEdges.size(); i++) {
        if (findSet(sortedEdges[i].src) != findSet(sortedEdges[i].dest)) {
            result.push_back(edge());

            long resultSize = result.size();

            result[resultSize - 1].src = sortedEdges[i].src;
            result[resultSize - 1].dest = sortedEdges[i].dest;
            result[resultSize - 1].weight = sortedEdges[i].weight;

            setUnion(sortedEdges[i].src, sortedEdges[i].dest);

            sum += sortedEdges[i].weight;
        }
    }

    return result;
}

int main () {
	FILE* input = fopen("apm.in", "r");
	FILE* output = fopen("apm.out", "w");

	fscanf(input, "%ld %ld", &N, &M);

	std::vector< edge > edges;

	long src, dest, weight;
    for (long i = 0; i < M; i++) {
        fscanf(input, "%ld %ld %ld", &src, &dest, &weight);

        edges.push_back(edge());

        edges[i].src = src;
        edges[i].dest = dest;
        edges[i].weight = weight;
    }

   	long kruscalSum = 0;
    std::vector<edge> result = kruskal(edges, kruscalSum);

    fprintf(output, "%ld\n", kruscalSum);
    fprintf(output, "%ld\n", result.size());

    for (unsigned long i = 0; i < result.size(); i++) {
    	fprintf(output, "%ld %ld\n", result[i].src, result[i].dest);
    }

	fclose(input);
	fclose(output);

	return 0;
}