#include <fstream>
#include <queue>

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

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;
}