#include<fstream>
#include<algorithm>
#define dmax 400003
#define nmax 200003
using namespace std;
ifstream f("apm.in"); ofstream g("apm.out");
int n, m,nr,j,cost, sol[nmax], T[nmax], H[nmax];

struct muchie
{   int a,b;
    short int c;//
}   muchia[dmax];

int cmp(muchie x, muchie y)
{    return x.c < y.c; }

void reuneste_arb(int a, int b)
{
    while(T[a] != 0)   a = T[a];
    while(T[b] != 0)   b = T[b];

    if(H[a] == H[b]) { T[a] = b; H[b]++; }
    else if(H[a] < H[b])  T[a] = b;
         else  T[b] = a;
}

bool verif(int a, int b)
{
    while(T[a] != 0)   a = T[a];
    while(T[b] != 0)   b = T[b];
    return (a==b);
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++) f>>muchia[i].a>>muchia[i].b>>muchia[i].c;
    sort(muchia+1, muchia+m+1, cmp);

    for(int i=1; i<=n; i++) H[i] = 1;//Kruskal
    j=1; cost=0;
    while(nr < n-1)
    {
        while(verif(muchia[j].a, muchia[j].b)) j++;
        nr++;
        sol[nr] = j;
        cost += muchia[j].c;
        reuneste_arb(muchia[j].a, muchia[j].b);
    }
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(int i=1; i<n; i++)g<<muchia[sol[i]].a<<" "<<muchia[sol[i]].b<<'\n';
    return 0;
}