//
// Created by Radu Buzas on 08.11.2022.
//

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

using namespace std;

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

vector<vector<pair<int, int>>> graph;
vector<pair<int, int>> sol;
int n, m, costTotal;

struct muchie{
    int cost, x, y;
    bool operator<(const muchie o) const{
        return ((this->cost) > o.cost);
    }
};

void prim(int x){
    vector<bool> visited(n+1);
    visited[x] = 1;
    priority_queue<muchie> q;
    for(auto m : graph[x]) {
        muchie V;
        V.cost = m.second;
        V.y = m.first;
        V.x = x;
        q.push(V);
    }
    while (!q.empty()){
        muchie k = q.top();
        q.pop();
        if(visited[k.y] == 0) {
            sol.push_back({k.x, k.y});
            costTotal += k.cost;
            visited[k.y] = 1;
            for (auto m: graph[k.y]) {
                muchie V;
                V.cost = m.second;
                V.y = m.first;
                V.x = k.y;
                q.push(V);
            }
        }
    }
}

int main(){
    in >> n >> m;
    graph.resize(n+1);
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        in >> x >> y >> c;
        graph[x].push_back({y, c});
        graph[y].push_back({x, c});
    }
    prim(1);
    out << costTotal << '\n';
    out << sol.size() << '\n';
    for (auto x : sol) {
        out << x.second << ' ' << x.first << '\n';
    }

}