#include <fstream>
#include <algorithm>
using namespace std;
struct muchie
{
    short x,y,c;
}u[400001];
struct ales
{
    short x,y;
}a[200001];
int l[200001],m,n,ct;
void citeste()
{
    ifstream f("apm.in");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>u[i].x>>u[i].y>>u[i].c;
    }
    f.close();
}
inline bool comp(muchie a, muchie b)
{
    return (a.c<b.c);
}
void kruskal()
{
    int i=1,k=0;
    while(k<n-1)
    {
        if(l[u[i].x]!=l[u[i].y])
        {
            a[++k].x=u[i].x;
            a[k].y=u[i].y;
            ct+=u[i].c;
            for(int j=1;j<=n;j++)
                if(l[j]==l[u[i].x]) l[j]=l[u[i].y];
        }
        i++;
    }
}
void afis()
{
    ofstream g("apm.out");
    g<<ct<<endl<<n-1<<endl;
    for(int i=1;i<n;i++)
        g<<a[i].x<<" "<<a[i].y<<endl;
    g.close();
}
int main()
{
    citeste();
    sort(u+1,u+m+1,comp);
    for(int i=1;i<=n;i++) l[i]=i;
    kruskal();
    afis();
    return 0;
}