#include <fstream>
#include <algorithm>
using namespace std;
ifstream f1("apm.in");
ofstream f2("apm.out");
#define MX 200100

struct edge
{
    int x,y, cost;
};

int n, m, tata[MX], k_apm, cost_min;
edge E[2*MX];

void join(int x, int y)
{
    while ( tata[x] )
        x= tata[x];

    while ( tata[y] )
        y= tata[y];

    tata[y]=x;
}

bool same_set(int x, int y)
{
    while ( tata[x] )
        x= tata[x];

    while ( tata[y] )
        y= tata[y];

    return x == y;
}

int ind[2*MX], ind1[2*MX];

void interclass(int st, int dr, int m)
{
    int i= st, j= m+1, k=st;

    while ( i<=m && j<=dr )
        if ( E[ ind[i] ].cost <= E[ ind[j] ].cost )
            ind1[k++]= ind[i++];
        else
            ind1[k++]= ind[j++];

    while ( i<=m )
        ind1[k++]= ind[i++];

    while ( j<=dr )
        ind1[k++]= ind[j++];

    for (i=st; i<=dr; i++)
        ind[i]= ind1[i];
}

void merge_sort(int st, int dr)
{
    if ( st>=dr )
        return;

    int m= (st+dr)/2;

    merge_sort(st,m);
    merge_sort(m+1,dr);

    interclass(st,dr,m);
}

int main()
{
    int i;
    f1>>n>>m;

    for (i=1; i<=m; i++)
        f1>>E[i].x>>E[i].y>>E[i].cost;

    for (i=1; i<=m; i++)
        ind[i]= i;

    merge_sort(1,m);

    for (i=1; i<=m; i++)
        if ( !same_set(E[ ind[i] ].x, E[ ind[i] ].y) )
        {
            join(E[ ind[i] ].x, E[ ind[i] ].y);
            ind1[++k_apm]= ind[i];
            cost_min+= E[ ind[i] ].cost;
        }

    f2<<cost_min<<"\n"<<k_apm<<"\n";
    for (i=1; i<= k_apm; i++)
        f2<<E[ ind1[i] ].x<<" "<<E[ ind1[i] ].y<<"\n";

    f2.close();
    return 0;
}