#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
int n,m,muchie[200000][3],t[400000],rang[400000],cost,a[400000],b[400000],nr=0;
ifstream f("apm.in");
ofstream g("apm.out");

int multime (int n)
{
    if (t[n]!=n)
        t[n]=multime(t[n]);
    return t[n];
}
void reuneste (int i,int j)
{
    i=multime(i);
    j=multime(j);
    if (i==j)
        return;
    if (rang[i]>rang[j])
        t[i]=j;
    else
        t[j]=i;
    if (rang[i]==rang[j])
        rang[i]++;
}
int comp_muchie (const void *i,const void *j)
{
    return ((int*)i)[2]-((int*)j)[2];
}
void kruskal()
{
    int i,j,k,c;
    qsort(muchie,m,sizeof(muchie[0]),comp_muchie);
    for (i=1;i<=n;i++)
        {
            t[i]=i;
            rang[i]=0;
        }
    for (k=0;k<m;k++)
        {
            i=muchie[k][0];
            j=muchie[k][1];
            c=muchie[k][2];
            if (multime(i)==multime(j))
                continue;
            reuneste(i,j);
            cost+=c;
            a[nr]=i;
            b[nr]=j;
            nr++;
        }
}
int main()
{
    int i;
    f>>n>>m;

    for (i=0;i<m;i++)

            f>>muchie[i][0]>>muchie[i][1]>>muchie[i][2];

    kruskal();
    g<<cost<<'\n'<<nr<<'\n';
    for (i=0;i<nr;i++)
        g<<a[i]<<" "<<b[i]<<'\n';
    return 0;
}