#include <iostream>
#include <stdio.h>
#include <algorithm>
#define max_m 400002
#define max_n 200002
using namespace std;
FILE *f,*g;
struct edges
{
    int x,y,c;
}muchie[max_m];
int t[max_n], rang[max_n],ok[max_n],sol[max_m][2];
int m,n;
bool cmp(edges &p, edges &q)
{
    return p.c<q.c;
}
void read()
{
    fscanf(f,"%d %d",&n,&m);
    for(int i=1; i<=m; i++)
        fscanf(f,"%d %d %d",&muchie[i].x, &muchie[i].y, &muchie[i].c);
    sort(muchie+1,muchie+m+1,cmp);
    for(int i=1; i<=n; i++)
    {
        t[i]=i;
        rang[i]=0;
    }
}
int multime(int node)
{
    if(t[node]!=node)
        t[node]=multime(t[node]);
    return t[node];
}
void reuneste(int i,int j)
{
    i=multime(i);
    j=multime(j);
    if (i==j) return;
    if (rang[i]<rang[j])
        t[i]=j;
    else
        t[j]=i;
    if (rang[i]==rang[j])
        rang[i]++;
}

int main()
{   int q=0,i,j,cost,rez=0;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    read();
    for(int l=1;l<=n;l++)
        ok[l]=false;
    for(int l=1; l<=m; l++)
    {   i=muchie[l].x;
        j=muchie[l].y;
        cost=muchie[l].c;
        if(multime(i)!=multime(j))
        {
            reuneste(i,j);
            rez+=cost;
            q++;
            sol[q][0]=i;
            sol[q][1]=j;

        }
    }
    fprintf(g,"%d\n%d\n",rez,q);
    for (int i=1; i<=q; i++)
        fprintf(g,"%d %d\n",sol[i][1],sol[i][0]);
    return 0;
}