#include <fstream>

using namespace std;

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

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

int n, m, vizv[100000], vizm[100000], 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;
}

bool cmp(muchie x, muchie y)
{
    return x.c<y.c;
}

void prim()
{
    sort(a, a+m, cmp);
    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;
}