#include <iostream>
#include <fstream>
using namespace std;
int x[100][100],d[100],jart[100],os[100],inf=1000;
int main()
{
    int i,j,n,m,a,b,c,kcs,S=0;
    bool vege=false;
    ifstream f;
    ofstream ki;
    f.open("apm.in");
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>a>>b>>c;
        x[a][b]=c;
        x[b][a]=c;
    }
    f.close();
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(x[i][j]==0){
                x[i][j]=inf;
            }
            x[i][i]=0;
        }
    }
    kcs=1;
    for(i=1;i<=n;i++){
        d[i]=inf;
        os[i]=kcs;
    }
    os[kcs]=0;
    d[kcs]=0;
    int db=0;
    while(!vege){
        int mincs=1,mind=inf;
        for(i=1;i<=n;i++){
            if(mind>d[i]&&!jart[i]){
                mind=d[i];
                mincs=i;
            }
        }

    if(mind==inf)vege=true;
    else{
        jart[mincs]=1;
        S+=d[mincs];
        db++;
        for(i=1;i<=n;i++){
            if(x[mincs][i]<d[i]&&!jart[i]){
                d[i]=x[mincs][i];
                os[i]=mincs;
            }
        }
    }
    }
    ki.open("apm.out");
    ki << S << endl;
    ki << n-1 << endl;
    for(i=1;i<=n;i++){
            if(os[i]){
        ki<<i<<" "<<os[i]<<endl;}
    }
    ki.close();


}