#include <fstream>
#include <deque>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cstring>
#include <climits>

#define MOD 104659

using namespace std ;

ifstream cin ("apm.in") ;
ofstream cout ("apm.out") ;

/// sortam muchiile in functie de cost, si folosind paduri de multimi disjuncte selectam doar muchiile care leaga doua paduri nelegate,

int n, aux ;

int tati[200009], nivele[200009] ;

int tatal_suprem(int nod) /// ts cu aplatizare arboriala integrata
{
    if(!tati[nod])
    {
        aux = nod ;

        return nod ;
    }

    int loc = tatal_suprem(tati[nod]) ;

    tati[nod] = aux ;

    return loc ;
}

bool query(int a, int b)
{
    return (tatal_suprem(a) == tatal_suprem(b)) ;
}

void merg(int a, int b)
{
    if(query(a, b))return ;

    int tsa = tatal_suprem(a) ;
    int tsb = tatal_suprem(b) ;

    if(nivele[tsa] < nivele[tsb])
    {
        tati[tsa] = tsb ;
    }
    if(nivele[tsa] > nivele[tsb])
    {
        tati[tsb] = tsa ;
    }
    if(nivele[tsa] == nivele[tsb])
    {
        tati[tsa] = tsb ;

        nivele[tsa] ++ ;
        nivele[tsb] ++ ;
    }
}

vector<pair<int, pair<int, int> > > v ;

int main()
{
    int q ;

    cin >> n >> q ;

    while(q --)
    {
        int a, b, c ;

        cin >> a >> b >> c ;

        v.push_back({c, {a, b}}) ;
    }

    sort(v.begin(), v.end()) ;

    vector<pair<int, int> > fin ;
    int rez = 0 ;

    for(int f = 0 ; f < v.size() ; f ++)
        if(!query(v[f].second.first, v[f].second.second)) /// sa return 1 daca sunt in aceeasi padure
            rez += v[f].first, fin.push_back(v[f].second), merg(v[f].second.first, v[f].second.second) ;

    cout << rez << endl ;

    cout << fin.size() << endl ;

    for(int f = 0 ; f < fin.size() ; f ++)
        cout << fin[f].first << " " << fin[f].second << '\n' ;


    return 0 ;
}