#include <iostream>
#include<math.h>
#include<vector>
#include<fstream>
#include<algorithm>
#include<deque>
#include<queue>
using namespace std;
#define lll long long
ifstream fin("trees.in");
ofstream fout("trees.out");
#define pb push_back
#define mp make_pair
#define eb emplace_back
const int NR = 2e5 + 10 , oo = 2e9;
int n , m ;
vector < int > d ( NR , oo ) ;
struct node{
    int nod , cost , tata;
};
struct cmp  {
    bool operator() ( node i , node j ) {
        return i.cost > j.cost ;
    }
};
ifstream in("apm.in");
ofstream out("apm.out");
priority_queue < node,vector<node>,cmp> pq;
vector < pair < int , int > > v [ NR ] , sol ;
int viz [ NR ] ;
signed main() {
    int x , y , i , z ;
    in >> n >> m ;
    for ( i = 1 ; i <= m ; ++ i )   {
        in >> x >> y >> z ;
        v [ x ].eb( mp( y , z ) ) ;
        v [ y ].eb( mp( x , z ) ) ;
    }
    d [ 1 ] = 0 ;
    node temp ;
    temp.cost = 0;
    temp.nod = 1;
    temp.tata = -1;
    pq.push(temp);
    int nod ;
    lll sum = 0 ;
    while ( !pq.empty() )   {
        nod = pq.top().nod ;
        node temp2 = pq.top();
        pq.pop();
        if ( viz [ nod ] )
            continue ;
        sum += temp2.cost;
        viz [ nod ] = 1 ;
        sol.pb(mp(temp2.nod,temp2.tata));
        for  ( auto it : v [ nod ] )    {
            if ( !viz [ it.first ] )  {
                temp.nod = it.first ;
                temp.cost = it.second ;
                temp.tata = nod ;
                pq.push(temp);
            }
        }
    }
    out << sum << '\n' ;
    out << sol.size() - 1 << '\n' ;
    for ( auto it : sol )   {
        if ( it.second != -1 )
        out << it.second << ' ' << it.first << '\n' ;
    }
    return 0;
}