#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>

using namespace std;

#define MAXN 200005
vector<pair<int, pair<int, int> > > edges;
int T[MAXN];
bool used[MAXN];
int N, M, numUsed, minCost;

int find(int x) {
    int root = x;
    while(root != T[root])
        root = T[root];

    while(x != root) {
        int y = T[x];
        T[x] = root;
        x = y;
    }

    return root;
}

void unite(int x, int y) {
    rand() & 1 ? T[x] = y : T[y] = x;
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out","w", stdout);

	scanf("%d %d", &N, &M);

	for(int i = 0; i < M; i++) {
	    static int x, y, c;
	    scanf("%d %d %d", &x, &y, &c);

        edges.push_back(make_pair(c, make_pair(x, y)));
	}

    sort(edges.begin(), edges.end());

    for(int i = 1; i <= N; i++)
        T[i] = i;

    srand(time(NULL));

    numUsed = 0;
    minCost = 0;
    for(size_t i = 0; i < edges.size(); i++) {
        int x = edges[i].second.first;
        int y = edges[i].second.second;
        int c = edges[i].first;

        int fx = find(x);
        int fy = find(y);
        if(fx != fy) {
            unite(fx, fy);
            numUsed++;
            minCost += c;
            used[i] = true;
        }
    }

    printf("%d\n", minCost);
    printf("%d\n", numUsed);

    for(size_t i = 0; i < edges.size(); i++)
        if(used[i])
            printf("%d %d\n", edges[i].second.first, edges[i].second.second);

	return 0;
}