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

using namespace std;

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

int find_parent(int node, vector<int> &parent)
{
    if(parent[node] == node){
        return node;
    }
    parent[node] = find_parent(parent[node], parent);
    return parent[node];
}

void unite(int u, int v, vector<int> &parent)
{
    parent[u] = find_parent(v, parent);
}

int main()
{
    int N, M;
    fin >> N >> M;
    vector<pair<int, pair<int, int>>> edges;
    for(int i = 0; i < M; i++){
        int a, b, c;
        fin >> a >> b >> c;
        edges.push_back({c, {a, b}});
        edges.push_back({c, {b, a}});
    }
    sort(edges.begin(), edges.end());
    vector<int> parent(N+1, 0);
    for(int i = 1; i <= N; i++){
        parent[i] = i;
    }
    int cost = 0;
    vector<pair<int, int>> mst;
    for(int i = 0; i < edges.size(); i++){
        int u = edges[i].second.first;
        int v = edges[i].second.second;
        int c = edges[i].first;
        if(find_parent(u, parent) != find_parent(v, parent)){
            unite(u, v, parent);
            mst.push_back({u, v});
            cost += c;
        }
        if(mst.size() == N-1){
            break;
        }
    }
    fout << cost << endl << N-1 << endl;
    for(auto it : mst){
        fout << it.first << " " << it.second << endl;
    }
    return 0;
}