#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii
{
    int x,y,c;
} muchie[400001],muchiesol[200001];
bool compar(muchii m1,muchii m2) { return m1.c < m2.c; }
int graf[200001],m,n,i,k,cost,caut,j;
int main()
{
    f>>n;
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>muchie[i].x>>muchie[i].y>>muchie[i].c;
    }
    for(i=1;i<=n;i++)
        graf[i]=i;
    sort(muchie+1,muchie+m+1,compar);
    i=1;
    k=0;
    while(k<n-1&&i<=m)
    {
        if(graf[muchie[i].x]!=graf[muchie[i].y])
        {
            k++;
            cost=cost+muchie[i].c;
            muchiesol[k]=muchie[i];
            caut=graf[muchie[i].y];
            for(j=1;j<=n;j++)
            {
                if(graf[j]==caut) graf[j]=graf[muchie[i].x];
            }
        }
        i++;
    }
    g<<cost<<'\n';
    g<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        g<<muchiesol[i].x<<" "<<muchiesol[i].y<<'\n';
    }
    return 0;
}