#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m, pa[200005], cst, cnt;

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

priority_queue < pair < int, pair < int, int > > , vector < pair < int, pair < int, int > > > , greater < pair < int, pair < int, int > > > > pq;

pair < int, pair < int, int > > aux;

pair < int , int > rsp[400005];

int dsu ( int nod )
{
    if ( pa[nod] == nod )
    {
        return nod;
    }

    return pa[nod]  = dsu( pa[nod] );

}

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

    for ( int i = 1; i <= m ; i++ )
    {
        f>>aux.y.x>>aux.y.y>>aux.x;

        pq.push(aux);

    }

    for ( int i = 1; i <= n; i++)
    {
        pa[i] = i;
    }

    while ( !pq.empty() )
    {
        int a = dsu( pq.top().y.x );
        int b = dsu( pq.top().y.y );

        if ( a != b )
        {
            pa[a] = b;
            cst+=pq.top().x;
            rsp[++cnt] = { pq.top().y.x , pq.top().y.y };
        }

        pq.pop();

    }

    g<<cst<<'\n'<<cnt<<'\n';

    for ( int i = 1;  i <= cnt ; i++ )
    {
        g<<rsp[i].x<<" "<<rsp[i].y<<'\n';
    }


}