#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

/// alg lui Kruskal si alg lui Prim
/// sa se determine un subgraf de cost minim care sa aiba toate nodurile initiale si este arbore

/*
alg lui prim :

vector<pair<int, int> > m[200009], muchii ;

int n, viz[200009] ;
priority_queue<pair<int, long long> > pq ;

int prim(int nod)
{

    int s = 0 ;

    viz[nod] = 1 ;

    for(int f = 0 ; f < m[nod].size() ; f ++)
        pq.push({m[nod][f].second * -1, m[nod][f].first * 1000000 + nod}) ;

    while(pq.size())
    {
        int nod = pq.top().second / 1000000 ;
        int cost = pq.top().first ;
        int prev = pq.top().second % 1000000 ;

        pq.pop() ;

        if(!viz[nod])
        {
            viz[nod] = 1 ;

            s += cost * -1 ;

            muchii.push_back({prev, nod}) ;

            for(int f = 0 ; f < m[nod].size() ; f ++)
                pq.push({m[nod][f].second * -1, m[nod][f].first * 1000000 + nod}) ;
        }
    }

    return s ;
}

int main()
{
    int q ;

    cin >> n >> q ;

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

        cin >> a >> b >> c ;

        m[a].push_back({b, c}) ;

        m[b].push_back({a, c}) ;
    }

    cout << prim(1) << endl ;

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

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

    return 0;
}
*/

/// ne trebuie paduri de multimi disjuncte
/// sortam muchiile in functie de cost, cand gasim o muchie care uneste 2 noduri care sunt in 2 paduri diferite, adaugam muchia in rez

vector<pair<int, pair<int, int> > > m ;

vector<pair<int, int> > muchii ;

int tatal[200009], marime[200009] ;

int tat(int a)
{
    if(tatal[a] == 0)return a ;

    return tat(tatal[a]) ;
}

int query(int a, int b) /// da 1 daca sunt in paduri diferite
{
    if(tat(a) == tat(b))return 0 ;

    return 1 ;
}

void uneste(int a, int b)
{
    int ta = tat(a) ;
    int tb = tat(b) ;

    if(marime[ta] < marime[tb])
    {
        marime[tb] = max(marime[tb], marime[ta] + 1) ;

        tatal[ta] = tb ;
    }
    else
    {
        marime[ta] = max(marime[ta], marime[tb] + 1) ;

        tatal[tb] = ta ;
    }
}

int main()
{
    int q, n ;

    cin >> n >> q ;

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

        cin >> a >> b >> c ;

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

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

    int s = 0 ;

    for(int f = 0 ; f < m.size() ; f ++)
        if(query(m[f].second.first, m[f].second.second))
        muchii.push_back({m[f].second}),
        s += m[f].first,
        uneste(m[f].second.first, m[f].second.second) ;

    cout << s << endl << muchii.size() << endl ;

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

    return 0 ;
}