#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cmath>

#define MOD 666013
#define INT_MAX 1000000000

using namespace std ;

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

int tata[100009], depth[100009] ;

int tatals(int a)
{
    if(!tata[a])return a ;

    return tatals(tata[a]) ;
}

void uneste(int a, int b)
{
    int tsa = tatals(a) ;
    int tsb = tatals(b) ;

    if(depth[tsa] < depth[tsb])
    {
        tata[tsa] = tsb ;
    }
    else if(depth[tsb] < depth[tsa])
    {
        tata[tsb] = tsa ;
    }
    else
    {
        tata[tsb] = tsa ;

        depth[tsa] ++ ;
    }
}

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

int main()
{
    int n, q ;

    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, r = 0 ;

    for(int f = 0 ; f < m.size() ; f ++)
    {
        int st = m[f].second.first, dr = m[f].second.second ;

        if(tatals(st) != tatals(dr))
            uneste(st, dr), s += m[f].first, r ++ ;
        else m[f].first = INT_MIN ;
    }

    cout << s << endl ;

    cout << r << endl ;

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

    return 0 ;
}
/// 1990