#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 200000
#define MMAX 400000

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,parent[NMAX+5],nrelemente[NMAX+5],p1,p2,lrez,suma;
struct muchie{
    int x,y,cost;
} sir[MMAX+5];
pair <int,int> rez[NMAX+5];

int functie(int val){
    if(parent[val]==val){
        return val;
    }else{
        parent[val]=functie(parent[val]);
        return parent[val];
    }
}

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

int main() {
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>sir[i].x>>sir[i].y>>sir[i].cost;
    }
    for(int i=1;i<=n;i++){
        parent[i]=i;
        nrelemente[i]=1;
    }
    sort(sir+1,sir+m+1,cmp);
    for(int i=1;i<=m&&lrez<n-1;i++){
        p1=functie(sir[i].x);
        p2=functie(sir[i].y);
        if(p1!=p2){

            if(nrelemente[p1]<=nrelemente[p2]){
                nrelemente[p2]+=nrelemente[p1];
                parent[p1]=p2;
            }else{
                nrelemente[p1]+=nrelemente[p2];
                parent[p2]=p1;
            }
            lrez++;
            rez[lrez].first=sir[i].x;
            rez[lrez].second=sir[i].y;
            suma+=sir[i].cost;
        }
    }
    g<<suma<<'\n'<<lrez<<'\n';
    for(int i=1;i<=lrez;i++){
        g<<rez[i].first<<' '<<rez[i].second<<'\n';
    }
    f.close();
    g.close();
    return 0;
}