#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

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

class graf
{
    int n,m,cost;
    vector < pair < pair < int, int >, int > > M1;
    vector < pair < int, int > > M2;
    vector <int> N;
    int find_set(int x);

public:
    void citire();
    void Kruskal();
    void afisare();
};

int compare(pair < pair < int, int >, int >x, pair < pair < int, int >, int > y)
{
    return x.second<y.second;
}

void graf :: citire()
{

    f >> n >> m;
    for ( int i = 0; i < m; ++ i )
    {
        int x, y, c;
        f >> x >> y >> c;
        M1.push_back( make_pair( make_pair( x, y ), c ) );
    }
}

int graf::find_set(int i)
{
    if (N[i] == i) return i;
    N[i] = find_set(N[i]);
    return N[i];
}


void graf::Kruskal()
{
    sort(M1.begin(),M1.end(),compare);
    N.resize(n+1);
    for(int i=1; i<=n; i++) N[i]=i;

    int nrm=0;
    cost=0;
    for ( int i = 0; i < m && nrm < n - 1; i++ )
    {
        int a = find_set( M1[i].first.first);
        int b = find_set( M1[i].first.second );
        if ( a != b )
        {
            nrm++;
            cost = cost + M1[i].second;
            M2.push_back( make_pair( M1[i].first.first, M1[i].first.second ) );
            if ( a > b ) N[b] = a;
            else N[a] = b;
        }
    }
}

void graf::afisare()
{
    g << cost << '\n';
    g << n - 1 << '\n';
    int i;
    for(i=0; i<n-1; i++)
        g<<M2[i].first<<" "<<M2[i].second<<'\n';
}


int main()
{
    graf G;
    G.citire();
    G.Kruskal();
    G.afisare();
    return 0;
}