#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 200005;
const int MMAX = 400005;
struct idk{
    int x,y,cost;
};
idk a[MMAX];
int parinte[NMAX],dim[NMAX];
int n,m,afis[NMAX];
bool cmp(idk a,idk b){
    return a.cost < b.cost;
}
int get_root(int node){
    while(parinte[node]!=node){
        node=parinte[node];
    }
    return node;
}
void unesc(int node1,int node2){
    int r1=get_root(node1);
    int r2=get_root(node2);
    if(r1==r2) return;
    if(dim[r1]<=dim[r2]){
        parinte[r1]=r2;
        dim[r2]+=dim[r1];
    } else {
        parinte[r2]=r1;
        dim[r1]+=dim[r2];
    }
}
int main()
{
    fin >> n >> m;
    for(int i=1;i<=n;i++){
        parinte[i]=i;
        dim[i]=1;
    }
    for(int i=1;i<=m;i++){
        fin >> a[i].x >> a[i].y >> a[i].cost;
    }
    sort(a+1,a+m+1,cmp);
    int rasp=0,dim_afis=0;
    for(int i=1;i<=m;i++){
        int p1=get_root(a[i].x);
        int p2=get_root(a[i].y);
        if(p1!=p2){
            unesc(p1,p2);
            rasp+=a[i].cost;
            afis[++dim_afis]=i;
        }
    }
    fout << rasp << '\n';
    fout << n-1 << '\n';
    for(int i=1;i<=dim_afis;i++){
        fout << a[afis[i]].x << ' ' << a[afis[i]].y << '\n';
    }
    return 0;
}