#include <stdio.h>
#include <queue>
using namespace std;
#define IN "apm.in"
#define OUT "apm.out"
#define NMAX 200005

struct edge { int x; int y; int cost;};
struct cmp
{
    bool operator() (const edge &A, const edge &B)
    {
        return A.cost>B.cost;
    }
};
priority_queue <edge, vector<edge>, cmp> apm;
vector<edge> final;
int n,m,total;
int comp[NMAX],h[NMAX];

int gaseste(int);
void uneste(int,int);
int main()
{
    FILE * fin=fopen(IN,"r");
    FILE * fout=fopen(OUT,"w");

    int i,r1,r2,selectate; edge muchie,element;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        comp[i]=i; h[i]=1;
        fscanf(fin,"%d%d%d",&element.x,&element.y,&element.cost);
        apm.push(element);
    }

    selectate=0;
    while(selectate<n-1)
    {
        muchie=apm.top(); apm.pop();
        r1=gaseste(muchie.x);
        r2=gaseste(muchie.y);
        if(r1!=r2)
        {
            selectate++;
            total+=muchie.cost;
            uneste(r1,r2);
            final.push_back(muchie);
        }
    }
    fprintf(fout,"%d\n",total);
    fprintf(fout,"%d\n",final.size());
    for(i=0;i<final.size();i++)
        fprintf(fout,"%d %d\n",final[i].x,final[i].y);


    fclose(fin);
    fclose(fout);
    return 0;
}

int gaseste(int x)
{
    int alfa,y;
    for(alfa=x;comp[alfa]!=alfa;alfa=comp[alfa]);
    for(;comp[x]!=x;)
    {
        y=comp[x];
        comp[x]=alfa;
        x=y;
    }
    return alfa;
}

void uneste(int x, int y)
{
    if(h[x]>h[y])
        comp[y]=x;
    else
        comp[x]=y;
    if(h[x]==h[y])
        h[y]++;
}