#include <stdio.h>
#include <algorithm>
#include <vector>
#define inf 1000000000
using namespace std;
int n,m,x,y,c,i,j,r1,r2,cmin,t[200005],h[200005];
vector<int> sol;
struct muchie
{
    int x,y,c;
}e[400005];

bool comp(muchie a,muchie b)
{
    return a.c<b.c;
}

int root(int n)
{
    while (t[n]) n=t[n];
    return n;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
        scanf("%i%i%i",&e[i].x,&e[i].y,&e[i].c);

    j=0;
    sort(e+1,e+m+1,comp);
    for (i=1;i<n;i++)
    {
        r1=r2=0;
        while (r1==r2)
        {
            j++;
            r1=root(e[j].x);
            r2=root(e[j].y);
        }
        cmin+=e[j].c;
        sol.push_back(j);
        if (h[r1]>h[r2])
            t[r2]=r1;
        else if (h[r1]<h[r2])
            t[r1]=r2;
        else
        {
            t[r1]=r2;
            h[r2]++;
        }
    }
    printf("%i\n%i\n",cmin,n-1);
    for (i=0;i<n-1;i++)
        printf("%i %i\n",e[sol[i]].x,e[sol[i]].y);
    fclose(stdin);
    fclose(stdout);
    return 0;
}