#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y,c;
};
muchie a[400001];
int n,h[200001],sol[200001][2],m,s,nr;
bool cmp( const muchie &a, const muchie &b)
{
    if(a.c<b.c) return 1;
    return 0;
}
void completare(int x, int y)
{
    for(int i=1; i<=n; i++)
        if(h[i]==x) h[i]=y;
}
int main()
{
    int i,j;
    f>>n>>m;
    for(i=1; i<=n; i++)
    {
        h[i]=i;

    }
    for(i=1; i<=m; i++)
    {
        f>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+m+1,cmp);
    i=1,j=0;
    while(j<n-1)
    {
        if(h[a[i].x]!=h[a[i].y])
        {
            s=s+a[i].c;
            j++;
            sol[j][0]=a[i].x;
            sol[j][1]=a[i].y;
            completare(h[a[i].y],h[a[i].x]);
        }
        i++;
    }
    g<<s<<'\n';
    g<<j<<'\n';
    for(i=1; i<=j; i++)
        g<<sol[i][0]<<' '<<sol[i][1]<<'\n';
}