/*
    Initial fiecare nod se afla intr-o componenta conexa proprie. La
    fiecare pas, se alege muchia de cost minim ce are extremitatile in
    2 componente conexe distincte. Cele 2 componente se reunesc.
*/
#include <bits/stdc++.h>

using namespace std;

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

int n,m,apm,k;
int c[200005];

struct muchie{int x,y,cost;
              bool a;}M[400005];

bool comp(muchie m1,muchie m2)
{
    if(m1.cost < m2.cost)return true;
    return false;
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i){
            f>>M[i].x>>M[i].y>>M[i].cost; ///VECTOR DE MUCHII
            c[i]=i;
    }

    sort(M+1,M+m+1,comp); ///SORTAM MUCHIILE IN FCT DE COST
    int i,cc;
    for(i=1;i<=m;++i)
        if(c[M[i].x]!=c[M[i].y]){  ///DACA MUCHIILE SE AFLA IN COMP DIFERITE
            apm+=M[i].cost;
            M[i].a=true;   ///MUCHIA I SE AFLA IN APM
            ///TOATE NODURILE DIN COMP Y SE MUTA IN COMP X
            cc=c[M[i].y];
            for(int j=1;j<=n;++j)
                if(c[j]==cc)c[j]=c[M[i].x];
            ++k;
            if(k==n-1)break;
        }

    g<<apm<<'\n';
    g<<n-1<<'\n';
    for(int i=1;i<=m;++i)
        if(M[i].a)g<<M[i].x<<' '<<M[i].y<<'\n';


    f.close(); g.close();
    return 0;
}