#include<bits/stdc++.h>
using namespace std;

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

struct muchie{
    int x, y, cost;
    friend bool operator >(const muchie&, const muchie&);
};

bool operator >(const muchie& m1, const muchie& m2)
{
    return m1.cost > m2.cost;
}

priority_queue< muchie, vector< muchie >, greater< muchie > >H;
vector< muchie >Sol;

int n, m, suma;
int tat[200001], h[200001];

int Find(int x)
{
    int r = x;
    int y, aux;
    while( tat[ r ] )
    {
        r = tat[ r ];
    }
    y = x;
    while( y != r )
    {
        aux = tat[ y ];
        tat[ y ] = r;
        y = aux;
    }
    return r;
}

void Union(int x, int y)
{
    if( h[ x ] > h[ y ] )
    {
        tat[ y ] = x;
    }
    else
    {
        tat[ x ] = y;
        if( h[ y ] == h[ x ])
        {
            h[ y ]++;
        }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++i)
    {
        muchie noua;

        f >> noua.x >> noua.y >> noua.cost;
        H.push( noua );
    }
    while(Sol.size() < n - 1)
    {
        muchie luata = H.top();
        int c1 = luata.x;
        int c2 = luata.y;
        H.pop();
        if( Find( c1 ) != Find( c2 ) )
        {
            Sol.push_back( luata );
            suma += luata.cost;
            Union(c1, c2);
        }
    }
    g << suma << '\n' << n - 1 << '\n';
    for(int i = 0 ; i < n - 1 ; ++i)
        g << Sol[ i ].x << ' ' << Sol[ i ].y << '\n';
}