#include<cstdio>
#include<algorithm>

using namespace std;

int n,m;
struct str
{
    int st;
    int dr;
    int val;
} muchii[400010];
int ct;

int res[400010];
int co,sum;

int tata[200010],sz[200010];

//******************

int comp(str a, str b)
{
    return a.val<b.val;
}

int is_connected(int nod1, int nod2)
{
    int tata1=nod1,tata2=nod2;
    while(tata1!=tata[tata1])
    {
        tata1=tata[tata1];
    }
    while(tata2!=tata[tata2])
    {
        tata2=tata[tata2];
    }
    //printf("** %d %d\n",tata1,tata2);
    if(tata1==tata2)
    {
        return 1;
    }
    return 0;
}

void connect(int nod1,int nod2)
{
    int tata1=nod1,tata2=nod2;
    while(tata1!=tata[tata1])
    {
        tata1=tata[tata1];
    }
    while(tata2!=tata[tata2])
    {
        tata2=tata[tata2];
    }

    if(sz[tata1]>sz[tata2])
    {
        sz[tata1]=max(sz[tata1],sz[tata2]+1);
        tata[tata2]=tata1;
        tata2=nod2;
        int keep;
        while(tata2!=tata[tata2])
        {
            keep=tata[tata2];
            tata[tata2]=tata1;
            tata2=keep;
        }
    }
    else
    {
        sz[tata2]=max(sz[tata2],sz[tata1]+1);
        tata[tata1]=tata2;
        tata1=nod1;
        int keep;
        while(tata1!=tata[tata1])
        {
            keep=tata[tata1];
            tata[tata1]=tata2;
            tata1=keep;
        }
    }
}

//**************

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        tata[i]=i;
    }

    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        muchii[i].st=x;
        muchii[i].dr=y;
        muchii[i].val=c;
    }
    sort(muchii+1,muchii+m+1,comp);
    /*for(int i=1;i<=m;i++)
    {
        printf("%d ",muchii[i].val);
    }*/
    for(int i=1;i<=m;i++)
    {
        if(is_connected(muchii[i].st,muchii[i].dr)==0)
        {
            connect(muchii[i].st,muchii[i].dr);
            co++;
            res[co]=i;
            sum+=muchii[i].val;
        }
    }
    printf("%d\n%d\n",sum,co);
    for(int i=1;i<=co;i++)
    {
        printf("%d %d\n",muchii[res[i]].st,muchii[res[i]].dr);
    }
}