#include <bits/stdc++.h>

using namespace std;

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

struct muchie{
    int x,y,c,viz;
}v[400001];

int n,m,S,nrcc,T[200001];

bool comp(muchie c1, muchie c2)
{
    return (c1.c<c2.c);
}

int Find(int nod)
{
    int rad=nod;
    while (T[rad]!=0)
    {
        rad=T[rad];
    }
    while (nod!=rad)
    {
        int aux=T[nod];
        T[nod]=rad;
        nod=aux;
    }
    return rad;
}

void Union(int nod1, int nod2)
{
    T[nod2]=nod1;
}

int main()
{
    in>>n>>m;
    nrcc=n;
    for (int i=1; i<=m; i++){
        in>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1, v+m+1, comp);
    for (int i=1; i<=m && nrcc>1; i++)
    {
        int a=Find(v[i].x),b=Find(v[i].y);
        if (a!=b)
        {
            Union(a, b);
            nrcc--;
            v[i].viz=1;
            S+=v[i].c;
        }
    }
    out<<S<<'\n'<<n-1<<'\n';
    for (int i=1; i<=m; i++)
    {
        if (v[i].viz)
        {
            out<<v[i].x<<" "<<v[i].y<<'\n';
        }
    }
}