#include<stdio.h>
#include<algorithm>

using namespace std;

FILE *fin,*fout;
int n,m;

long long int s;

bool viz[200001];

int poz[200001],p;

struct str
{
    int dl;
    int l;
    int val;
} vec[400001];

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

int v1,v2;
int tata[200001][2];

int main()
{
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");

    fscanf(fin,"%d %d",&n,&m);

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

    for(int i=1;i<=m;i++)
    {
        fscanf(fin,"%d %d %d",&vec[i].dl,&vec[i].l,&vec[i].val);
    }

    sort(vec+1,vec+m+1,comp);



    for(int i=1;i<=m;i++)
    {
        v1=tata[vec[i].dl][0];
        while(tata[v1][0]!=v1)
        {
            v1=tata[v1][0];
        }

        v2=tata[vec[i].l][0];
        while(tata[v2][0]!=v2)
        {
            v2=tata[v2][0];
        }

        if(v1!=v2)
        {
            s+=vec[i].val;
            p++;
            poz[p]=i;
            if(tata[v1][1]>tata[v2][1])
            {
                tata[v1][1]++;
                tata[v2][0]=v1;
            }
            else
            {
                tata[v2][1]++;
                tata[v1][0]=v2;
            }
        }
    }

    fprintf(fout,"%d\n",s);
    fprintf(fout,"%d\n",p);
    for(int i=1;i<=p;i++)
    {
        fprintf(fout,"%d %d \n",vec[poz[i]].dl,vec[poz[i]].l);
    }
}