#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

vector<vector<pair<int, int>>> graf;
int viz[200001];
vector<pair<int, int>> solutie;
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
void adaugare_muchii(int nod, priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> &pq1){
    viz[nod] = 1;
    for(auto &muchie:graf[nod]){
        int nod_adiacent = muchie.first;
        int cost = muchie.second;
        if(!viz[nod_adiacent])
        {
            pq1.push({cost, nod, nod_adiacent});
        }
    }
}
int main() {

    int n, m;
    f>>n>>m;
    graf.resize(n + 1);
    for(int i = 1; i<=m; i++){
        int x, y, cost;
        f>>x>>y>>cost;
        graf[x].push_back(make_pair(y, cost));
        graf[y].push_back(make_pair(x, cost));
    }
//    for(int i = 1; i<=n; i++){
//        cout<<i<<": ";
//        for(auto &pereche:graf[i]){
//            cout<<pereche.first<<" "<<pereche.second<<", ";
//        }
//        cout<<"\n";
//    }
    int nod_start = 1;
    int nr_muchii = 0;
    int cost_minim = 0;

    adaugare_muchii(nod_start, pq);
    while(!pq.empty()){
        vector<int> top = pq.top();
        pq.pop();
        int cost = top[0];
        int nod1 = top[1];
        int nod2 = top[2];
//        cout<<cost<<" "<<nod1<<" "<<nod2<<"\n";
        if(!viz[nod2])
        {
            nr_muchii += 1;
            viz[nod2] = 1;
            cost_minim += cost;
            solutie.emplace_back(nod1, nod2);
            adaugare_muchii(nod2, pq);
        }
    }
    g<<cost_minim<<"\n";
    g<<nr_muchii<<"\n";
    for(auto &pereche: solutie){
        g<<pereche.first<<" "<<pereche.second<<"\n";
    }
    return 0;
}