#include<iostream>
#include<fstream>
#include<algorithm>
#define Nmax 400005
#define Mmax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int i,j,n,m,v[Nmax];
long long cost;
struct arbore
{
    int x,y;
    long long c;
}a[Mmax],t[Nmax];
int cmp(arbore a,arbore b)
{
    return (a.c<b.c);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        {
            f>>a[i].x>>a[i].y>>a[i].c;
        }
    sort(a+1,a+m+1,cmp);
    v[a[1].x]=1;
    v[a[1].y]=1;
    cost=a[1].c;
    t[1].x=a[1].x;
    t[1].y=a[1].y;

    for(i=1;i<n-1;i++)
    {
        j=1;
        while(v[a[j].x]==v[a[j].y]) j++;
        if(v[a[j].x]==1)
            v[a[j].y]=1;
        else
            v[a[j].x]=1;
        cost += a[j].c;
        t[i+1].x=a[j].x;    t[i+1].y=a[j].y;
    }
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        g<<t[i].y<<" "<<t[i].x<<'\n';
    return 0;
}