#include <fstream>

using namespace std;

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

struct muchie{
    int x, y, c;
}a[100];

int n, m, vizv[100], vizm[100], ct=0, nr=0;

void citire()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
}

void sortare()
{
    for(int i=0; i<m-1; i++)
        for(int j=i+1; j<m; j++)
            if(a[i].c>a[j].c)
            {
                muchie aux=a[i];
                a[i]=a[j];
                a[j]=aux;
            }
}

void prim()
{
    sortare();
    vizv[a[0].x]=1;
    vizv[a[0].y]=1;
    vizm[0]=1;
    ct+=a[0].c;
    nr++;
    for(int i=1; i<n; i++)
    {
        int p=-1;
        for(int j=1; j<m; j++)
            if(vizm[j]==0 && (vizv[a[j].x] ^ vizv[a[j].y])==1)
            {
                p=j;
                break;
            }
        if(p!=-1)
        {
            vizv[a[p].x]=1;
            vizv[a[p].y]=1;
            vizm[p]=1;
            ct+=a[p].c;
            nr++;
        }
    }
}

void afisare()
{
    fout<<ct<<endl;
    fout<<nr<<endl;
    for(int i=0; i<m; i++)
        if(vizm[i]==1)
            fout<<a[i].x<<" "<<a[i].y<<endl;
}

int main()
{
    citire();
    prim();
    afisare();
    return 0;
}