#include <stdio.h>

using namespace std;

struct muchie
{
    int s,d,c;
} a[400004];
int t[200002],r[200002],sum,n,m,mch[200002],z;

void add_muchie(int x,int y,int c,int &i)
{
    a[i].s=x;
    a[i].d=y;
    a[i].c=c;
    i++;
}

void citire()
{
    freopen("apm.in","r",stdin);
    scanf("%d %d\n",&n,&m);
    int i=0;
    while(!feof(stdin))
    {
        int x,y,c;
        scanf("%d %d %d\n",&x,&y,&c);
        add_muchie(x,y,c,i);
    }
}

void init()
{
    for(int i=1;i<=n;i++)
        t[i]=i;
}

void sortare(int st,int dr)
{
    int i=st;
    int j=dr;
    muchie mu=a[(st+dr)/2];
    do
    {
        while(a[i].c<mu.c) i++;
        while(mu.c<a[j].c) j--;
        if(i<=j)
        {
            muchie t=a[i];
            a[i]=a[j];
            a[j]=t;
            i++;
            j--;
        }
    }
    while(i<=j);
    if(st<j) sortare(st,j);
    if(i<dr) sortare(i,dr);
}

int find(int x)
{
    if(t[x]==x)
        return x;
    t[x]=find(t[x]);
    return t[x];
}

void union_dr(int mx,int my)
{
    if(r[mx]<r[my])
    {
        t[my]=mx;
        return;
    }
    if(r[mx]<r[my])
    {
        t[mx]=my;
        return;
    }
    t[mx]=my;
    r[mx]++;
}

void rezolvare()
{
    for(int i=0;i<m;i++)
    {
        int mx=find(a[i].s);
        int my=find(a[i].d);
        if(mx!=my)
        {
            mch[z++]=i;
            sum+=a[i].c;
            union_dr(mx,my);
        }
    }
}

void afis()
{
    freopen("apm.out","w",stdout);
    printf("%d\n%d\n",sum,n-1);
    for(int i=0;i<n;i++)
    {
            printf("%d %d\n",a[mch[i]].s,a[mch[i]].d);
    }
}

int main()
{
    citire();
    init();
    sortare(0,m-1);
    rezolvare();
    afis();
    return 0;
}