#include <fstream>
#include <utility>
#include <climits>
#include <vector>
#include <set>
#include <list>
using namespace std;
#define mp make_pair
#define ft first
#define sd second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int main(){
    int n, m, i, x, y, c;
    fin>>n>>m;
    vector<list<pair<int, int> > > g(n+1);
    list<pair<int, int> > :: iterator it;
    for(i=1; i<=m; i++){
        fin>>x>>y>>c;
        g[x].push_back(mp(y, c));
        g[y].push_back(mp(x, c));
    }

    int total_cost = 0, start_node = 1;
    vector<int> dist(n+1, INT_MAX);
    dist[start_node] = 0;
    
    set<pair<int, pair<int, int> > > s;
    s.insert(mp(dist[start_node], mp(0, start_node)));
    
    vector<bool> selected(n+1, false);
    list<pair<int, int> > apm;
    
    while(!s.empty()){
        int cost = s.begin()->ft;
        int prev_node = s.begin()->sd.ft;
        int curr_node = s.begin()->sd.sd;
        s.erase(s.begin());
        if(selected[curr_node] == false){
            if(prev_node != 0)
                apm.push_back(mp(prev_node, curr_node));
            selected[curr_node] = true;
            total_cost += cost;
            for(it = g[curr_node].begin(); it != g[curr_node].end(); it++)
                if(dist[(*it).ft] > (*it).sd && selected[(*it).ft] == false){
                    s.erase(mp(dist[(*it).ft], mp(curr_node, (*it).ft)));
                    dist[(*it).ft] = (*it).sd;
                    s.insert(mp((*it).sd, mp(curr_node, (*it).ft)));
                }
        }
    }
    fout<<total_cost<<endl<<n-1<<endl;
    for(it = apm.begin(); it != apm.end(); it++)
        fout<<(*it).ft<<" "<<(*it).sd<<endl;
    return 0;
}