#include <algorithm>
#include <iostream>
#include <fstream>

using namespace std;
ifstream f("apm.in" );
ofstream g("apm.out");
struct t_node
{
    int v;
    t_node* father;
};

t_node element[100005];
int n, m;

int inaltime[100005];

int reuniune(int x, int y)
{
    t_node* actX = &element[x];
    t_node* actY = &element[y];

    while ( actX->father != NULL )
        actX = actX->father;
    while ( actY->father != NULL )
        actY = actY->father;

    if ( inaltime[actX->v] < inaltime[actY->v] )
        swap(actX, actY);


    inaltime[actX->v] = max(inaltime[actX->v], inaltime[actY->v] + 1);

    actY->father = actX;
}

int query(int x, int y)
{
    t_node* rootX = &element[x];
    t_node* rootY = &element[y];

    while ( rootX->father != NULL ) rootX = rootX->father;
    while ( rootY->father != NULL ) rootY = rootY->father;

    t_node* actX = &element[x];
    t_node* actY = &element[y];

    while ( actX->father != NULL )
    {
        actX->father = rootX;
        actX = actX->father;
    }
    while ( actY->father != NULL )
    {
        actY->father = rootY;
        actY = actY->father;
    }

    return actX == actY;
}

struct muchie
{
    int x;
    int y;
    int cost;
} muchii[400005];

bool operator<(const muchie a, const muchie b)
{
    return a.cost < b.cost;
}

int alese[400005];

int main()
{
    f >> n >> m;

    for ( int i=1; i<=m; i++ )
        f >> muchii[i].x >> muchii[i].y >> muchii[i].cost;

    sort(muchii+1, muchii+m+1);

    int cost = 0;
    for ( int i=1; i<=m; i++ )
    {
        if ( query(muchii[i].x, muchii[i].y) == 0 )
        {
            cost += muchii[i].cost;
            alese[i] = 1;
            reuniune(muchii[i].x, muchii[i].y);
        }
    }
    g << cost << '\n';
    g << n-1 << '\n';

    for ( int i=1; i<=m; i++ )
        if ( alese[i] == 1 )
            g << muchii[i].x << ' ' << muchii[i].y << '\n';
}