#include <fstream>
#include <algorithm>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int N = 200001;
int t[N], n, m, cnt, rez;

struct poz
{
    int i, j, c;
} M[N];
poz a[N];

void leaga (int a, int b)
{
    t[a]=t[b];
}

int radacina (int a)
{
    if(a == t[a]) return a;
    else return t[a] = radacina(t[a]);
}

void kruskal()
{
    int r1, r2;
    for (int i = 1; i <= m; i++)
    {
        r1 = radacina(M[i].i), r2 = radacina(M[i].j);
        if(r1 != r2)
        {
            rez += M[i].c;
            a[++cnt] = M[i];
            leaga(r1, r2);
        }
    }
}

int comp (poz a, poz b)
{
    return a.c < b.c;
}

int main()
{
    in >>n>>m;
    for (int i=1 ; i<=m ; i++)
    {
        int x, y, cost;
        in>>x>>y>>cost;
        M[i].i=x;
        M[i].j=y;
        M[i].c=cost;
    }

    sort (M+1, M+m+1, comp);
    for (int i=1 ; i<=n ; i++) t[i]=i;
    kruskal();
    out<<rez<<'\n'<<n-1<<'\n';
    for(int i=1 ; i<n ; i++)
    {
        out<<a[i].i<<" "<<a[i].j<<'\n';
    }
    return 0;
}