// Solutie de 100 de puncte
/*#include <fstream>
#include <map>

using namespace std;

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

struct A
{
    int x, y;
};

multimap < int, A > a;

int n, m, i, x, y, s, nr;
int t[200001], lg[200001];
A r[200001];

void citire();
void lipire();
bool acelasi();

int main()
{
    citire();
    for ( i = 1 ; i <= n ; i++ ) t[i] = i;
    while ( a.empty() == 0 )
    {
        x = a.begin() -> second.x;
        y = a.begin() -> second.y;
        if ( acelasi() == 0 )
        {
            nr++;
            s += a.begin() -> first;
            r[nr] = { x, y };
            lipire();
        }
        a.erase ( a.begin() );
    }

    fout << s << '\n' << nr << '\n';
    for ( i = 1 ; i <= nr ; i++ ) fout << r[i].x << ' ' << r[i].y << '\n';

    return 0;
}

void citire()
{
    int i, x, y, z;

    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> z;
        if ( x > y ) swap ( x, y );
        a.insert ( { z, { x, y } } );
    }
}

bool acelasi()
{
    int cx = x, cy = y;

    while ( t[cx] != cx ) cx = t[cx];
    while ( t[cy] != cy ) cy = t[cy];

    if ( cx == cy ) return 1;
    return 0;
}

void lipire()
{
    int cx = x, ccx = x, cy = y, ccy = y;

    while ( t[cx] != cx ) cx = t[cx];
    while ( t[cy] != cy ) cy = t[cy];

    if ( lg[cx] >= lg[cy] )
    {
        t[cy] = cx;
        while ( t[x] != x ) x = t[x], t[ccx] = cx, ccx = x;
        while ( t[y] != y ) y = t[y], t[ccy] = cx, ccy = y;
        if ( lg[cx] == lg[cy] ) lg[cx]++;
    }
    else
    {
        t[cx] = cy;
        while ( t[x] != x ) x = t[x], t[ccx] = cy, ccx = x;
        while ( t[y] != y ) y = t[y], t[ccy] = cy, ccy = y;
    }
}
*/

#include <fstream>
#include <vector>
#include <map>

using namespace std;

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

struct A
{
    int x, cost;
};

struct Muchie
{
    int x, y;
};

Muchie r[200001];

vector < A > v[200005];
multimap < int, Muchie > a;

int n, m;
bool viz[200005];


void citire();

int main()
{
    Muchie y;
    int i, x, Cost = 0, nr = 0;

    citire();

    viz[1] = 1;
    for ( i = 0 ; i < v[1].size() ; i++ ) a.insert ( { v[1][i].cost, { 1, v[1][i].x } } );
    while ( nr < n - 1 )
    {
        x = a.begin() -> first;
        y = a.begin() -> second;
        a.erase ( a.begin() );

        if ( viz[y.y] == 0 )
        {
            Cost += x;
            r[++nr] = y;
            viz[y.y] = 1;

            for ( i = 0 ; i < v[y.y].size() ; i++ ) if ( viz[v[y.y][i].x] == 0 ) a.insert ( { v[y.y][i].cost, { y.y, v[y.y][i].x } } );
        }
    }

    fout << Cost << '\n' << nr << '\n';
    for ( i = 1 ; i <= nr ; i++ ) fout << r[i].x << ' ' << r[i].y << '\n';

    return 0;
}

void citire()
{
    int i, x, y, z;

    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> z;
        v[x].push_back ( { y, z } );
        v[y].push_back ( { x, z } );
    }
}