#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
int tata[200005],h[200005];
struct muchie
{
    int x,y,c;
} v[400005];
struct cost
{
    int x,y;
} vc[200005];
int rad(int a)
{
    if(tata[a]==0)
        return a;
    return rad(tata[a]);
}
bool mycmp(muchie a,muchie b)
{
    if (a.c<b.c)
        return 1;
    return 0;
}
int main()
{
    int n,m,a,b,i,costt=0,k=0,j;
    f>>n>>m;
    for(i=1; i<=m; i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,mycmp);

    for(i=1; i<=m&&k<n-1; i++)
    {
        a=rad(v[i].x);
        b=rad(v[i].y);
        if(a!=b)
        {
            costt=costt+v[i].c;
            k++;
            vc[k].x=v[i].x;
            vc[k].y=v[i].y;
            if(h[a]>h[b])
            {
                h[a]=max(h[b]+1,h[a]);
                tata[b]=a;
            }
            else
            {
                h[b]=max(h[a]+1,h[b]);
                tata[a]=b;
            }

        }
    }
    g<<costt<<'\n'<<k<<'\n';
    for(i=1;i<=k;i++)
        g<<vc[i].x<<" "<<vc[i].y<<'\n';

    return 0;
}