#include<bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 2e5 + 5;
const int MMAX = 4e5 + 5;
struct edge{
    int x, y, c;
};
int n, m, sz, weight, H[NMAX], P[NMAX], MST[NMAX];
edge E[MMAX];

int find_parent(int node){
    if(P[node] == node)
        return node;
    return P[node] = find_parent(P[node]);
}

void merge_sets(int u, int v){
    if(H[u] > H[v])
        swap(u, v);
    P[u] = v;
    if(H[u] == H[v])
        ++H[v];
}

int main(){
    fin >> n >> m;

    for(int i = 0; i < m; ++i)
        fin >> E[i].x >> E[i].y >> E[i].c;

    for(int i = 1; i <= n; ++i)
        P[i] = i, H[i] = 0;

    sort(E, E + m, [](edge a, edge b){
        return a.c < b.c;
    });

    int i = 0, x, y;
    while(sz < n - 1){
        x = find_parent(E[i].x);
        y = find_parent(E[i].y);

        if(x != y){
            merge_sets(x, y);
            MST[++sz] = i;
            weight += E[i].c;
        }
        ++i;
    }

    fout << weight << '\n' << sz << '\n';

    for(int i = 1; i <= sz; ++i)
        fout << E[MST[i]].x << ' ' << E[MST[i]].y << '\n';
}