#include <bits/stdc++.h>

using namespace std;

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

int n,m;

struct muchie{
    int x;
    int y;
    int cost;
};

muchie G[200005];
int T[200005];
int R[200005];
int Sol[200005];

bool cmp(muchie a,muchie b){
    if(a.cost < b.cost){
        return 1;
    }
    return 0;
}

int findtata(int a){
    while(a != T[a]){
        a = T[a];
    }
    return a;
}

void unire(int a, int b){
    if(R[a] < R[b]){
        T[a] = b;
    }
    if(R[b] < R[a]){
        T[b] = a;
    }
    if(R[b] == R[a]){
        T[b] = a;
        R[a]++;
    }
}

int main(){
    int i,j;
    int a,b,cant = 0,k=0;
    fin>>n>>m;
    for(i = 1; i <= m; i++){
        fin>>G[i].x>>G[i].y>>G[i].cost;
    }
    sort(G+1, G+m+1, cmp);
    for(i = 1; i <= m; i++){
        T[i] = i;
    }
    for(i = 1; i <= m; i++){
        a = findtata(G[i].x);
        b = findtata(G[i].y);
        if(a != b){
            unire(a,b);
            cant += G[i].cost;
            Sol[++k] = i;
        }
    }
    fout<<cant<<'\n';
    fout<<k<<'\n';
    for(i = 1; i <= k; i++){
        fout<<G[Sol[i]].y<<" "<<G[Sol[i]].x<<'\n';
    }
    return 0;
}