#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int tt[200014], rg[200014], n, m;
int sol;
bitset < 400009 > viz ;

struct noduri
{
    int x, y, cost;
    void sett(int unu, int doi, int trei)
    {
        x=unu;
        y=doi;
        cost=trei;
    }
};
noduri  q[400014];
bool cmp(noduri a, noduri b)
{
    return a.cost<b.cost;
}
int stramos(int nod)
{
    int r=nod;
    for(;tt[r]!=r;r=tt[r]);
    while(tt[nod]!=nod)
    {
        int aux=tt[nod];
        tt[nod]=r;
        nod=aux;
    }
    return r;
}
void unire(int a, int b)
{
    a=stramos(a);
    b=stramos(b);
    if(a==b)
        return ;
    if(rg[a]<rg[b])
        swap(a, b);
    rg[a]+=rg[b];
    tt[b]=a;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        rg[i]=1;
        tt[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int tip, a, b;
        fin>>tip>>a>>b;
        q[i].sett(tip, a, b);
    }
    sort(q+1, q+1+m, cmp);
    for(int i=1;i<=m;i++)
    {
        if(stramos(q[i].x)==stramos(q[i].y))
            continue;
        unire(q[i].x, q[i].y);
        sol=sol+q[i].cost;
        viz[i]=1;
    }
    fout<<sol<<'\n';
    fout<<n-1<<'\n';
    for(int i=1;i<=m;i++)
        if(viz[i])
            fout<<q[i].x<<' '<<q[i].y<<'\n';
    return 0;
}