#include <fstream>
#include <algorithm>
using namespace std;

#define nmax 100

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

struct roxi{
    int v1,v2;
    int cost;};

roxi x[nmax];
roxi sol[nmax];

int n,m;
int viz[nmax];

void citire(roxi x[nmax],int &n,int &m){
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        {fin>>x[i].v1;
        fin>>x[i].v2;
        fin>>x[i].cost;}}
int compara(roxi a, roxi b){
    if(a.cost<b.cost)
        return 1;
    else
        return 0;
    }

int componenta(int i){
    if(i==viz[i])
        return i;
    else
    {viz[i]=componenta(viz[i]);
    return viz[i];}}

void reuniune(int a,int b){
    viz[componenta(b)]=componenta(a);
}
int main()
{
    citire(x,n,m);
    sort(x+1,x+m+1,compara);
    for(int i=1;i<=n;i++)
        viz[i]=i;
    int c=1;
    int costf=0;
    for(int i=1;i<=m;i++)
        if(componenta(x[i].v1)!=componenta(x[i].v2)){
            sol[c]=x[i];
            c++;
            costf+=x[i].cost;
            reuniune(x[i].v1,x[i].v2);}
    fout<<costf<<"\n"<<n-1<<"\n";
    for(int i=1;i<=c;i++)
        fout<<sol[i].v1<<" "<<sol[i].v2<<"\n";


    return 0;
}