#include <algorithm>
#include <fstream>
using namespace std;
struct muchie
{
    int x,y,c;
}u[400001];
struct M
{
    int x,y;
}a[400001];
int m,n,l[200001];
long 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();
}
int comp(muchie& a, muchie& b)
{
    return (a.c<b.c);
}
template <typename Iterator>
void heap_sort(Iterator a, Iterator b)
{
    make_heap(a, b,comp);
    sort_heap(a, b,comp);
}
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();
    heap_sort(u+1,u+m+1);
    for(int i=1;i<=n;i++)
        l[i]=i;
    int k=0,i=1;
    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;
            int w=l[u[i].x],v=l[u[i].y];
            for(int j=1;j<=n;j++)
                if(l[j]==v)l[j]=w;
        }
        i++;
    }
    afis();
    return 0;
}