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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie{
    int a, b, w;

    bool operator>(Muchie b) const{
        return this -> w > b.w;
    }
};

int main(){
    int n, m, x, y, c;

    fin >> n >> m;

    // citim graful
    vector<vector<pair<int, int>>> adjList(n + 1);
    while (fin >> x >> y >> c) {
        adjList[x].push_back({y, c});
        adjList[y].push_back({x, c});
    }

    vector<bool> vizitat(n + 1, false);
    priority_queue<Muchie, vector<Muchie>, greater<Muchie>> pq;

    int nodStart = 1;
    vizitat[nodStart] = true;

    // adaugam vecinii nodului de start in pq
    for (pair<int, int> vecin : adjList[nodStart]){
        pq.push({nodStart, vecin.first, vecin.second});
    }

    int costTotal = 0;
    vector<Muchie> rez;

    while (pq.size()){
        // selectam cea mai mica muchie care leaga un nod de apcm curent
        Muchie muchieMinima = pq.top();
        pq.pop();

        if (vizitat[muchieMinima.b])    // necesar pt ca o sa avem mai multe muchii pt acelasi nod
            continue;

        vizitat[muchieMinima.b] = true;

        rez.push_back(muchieMinima);
        costTotal += muchieMinima.w;

        for (pair<int, int> vecin : adjList[muchieMinima.b]){
            if (!vizitat[vecin.first]){
                pq.push({muchieMinima.b, vecin.first, vecin.second});
            }
        }
    }

    fout << costTotal << endl;
    fout << rez.size() << endl;
    for (Muchie m : rez){
        fout << m.a << " " << m.b << endl;
    }

}