#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector < pair <int,int> > v[20000];

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

bool viz[20000];

int tata[20000],cmin[20000],n,m,suma,n_c;

void citire()
{
    f>>n>>m;
    n_c=n;
    int i,x,y,c;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    for(i=1;i<=n;i++)
    {
        cmin[i]=2000;
        tata[i]=1;
    }
    for(i=0;i<v[1].size();i++)
        cmin[v[1][i].first]=v[1][i].second;
    tata[1]=0;
    viz[1]=true;
    n--;
}

void afisare()
{
    for(int i=2;i<=n_c;i++)
        g<<tata[i]<<" "<<i<<'\n';


}
int main()
{
    int min,nod,i;
    citire();
    while(n)
    {
        min=2000;
        nod=-1;
        for(i=1;i<=n_c;i++)
            if(!viz[i]&&min>cmin[i])
            {

                min=cmin[i];
                nod=i;
            }
        viz[nod]=true;
        n--;
        for(i=0;i<v[nod].size();i++)
            if(!viz[v[nod][i].first]&&cmin[v[nod][i].first]>v[nod][i].second)
            {
                tata[v[nod][i].first]=nod;
                cmin[v[nod][i].first]=v[nod][i].second;
            }

    }
    for(i=2;i<=n_c;i++)
        suma+=cmin[i];
    g<<suma<<'\n'<<n_c-1<<'\n';
    afisare();
    return 0;
}