#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int u,v,c;
} e[200001];
int l[200001],n,m;
struct afis
{
    int a,b;
}x[200001];
muchie aux;
void Quicksort (int s, int d)
{
    int i=s, j=d, pivot=e[(i+j)/2].c;
    while(i<=j)
    {
        while(e[i].c<pivot)
            i++;
        while(e[j].c>pivot)
            j--;
        if(i<=j)
        {
            aux=e[i];
            e[i]=e[i+1];
            e[i+1]=aux;
            i++, j--;
        }
    }
    if(s<j)
        Quicksort(s,j);
    if(i<d)
        Quicksort(i,d);
}

void citire()
{
    int i;
    f>>n;
    f>>m;
    for(i=1; i<=m; i++)
        f>>e[i].u>>e[i].v>>e[i].c;
}

int main()
{
    int k,ultim,i,u,v,ct,ind,ms,lu,lv,q=0;
    citire();
    for(i=1; i<=n; i++)
        l[i]=i;
    Quicksort(1, n);
    ct=0;
    ms=0;
    ind=0;
    while(ms<n-1)
    {
        do
            ind++;
        while(l[e[ind].u]==l[e[ind].v]);
        u=e[ind].u;
        lu=l[u];
        v=e[ind].v;
        lv=l[v];
        q++;
        x[q].a=u; x[q].b=v;
        ct=ct+e[ind].c;
        ms++;
        for(i=1; i<=n; i++)
            if(l[i]==lu)
                l[i]=lv;
    }
    g<<ct<<"\n"<<q<<"\n";
    for(i=1;i<=q;i++)
        g<<x[i].a<<" "<<x[i].b<<"\n";
    return 0;
}