#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#define MAX_N 200005
using namespace std;

// cost, nextt
vector<pair<int, int> > from[MAX_N];
vector<pair<int, int> > result;
// cost, destination
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;
int total;
bool visited[MAX_N];

void visit(int a)
{
    visited[a] = true;
    for (auto j: from[a])
        pq.push({j.first, j.second, a});
}

int main()
{
    FILE *fin = fopen("apm.in", "r");
    FILE *fout = fopen("apm.out", "w");
    int n, m;
    fscanf(fin, "%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        fscanf(fin, "%d %d %d", &a, &b, &c);
        a--; b--;
        from[a].push_back({c, b});
        from[b].push_back({c, a});
    }
    visit(0);
    while (!pq.empty()) {
        auto tp = pq.top();
        pq.pop();
        if (!visited[get<1>(tp)]) {
            total += get<0>(tp);
            result.push_back({get<2>(tp), get<1>(tp)});
            visit(get<1>(tp));
        }
    }

    fprintf(fout, "%d\r\n", total);
    fprintf(fout, "%lu\r\n", result.size());
    for (auto j: result)
        fprintf(fout, "%d %d\r\n", j.first + 1, j.second + 1);
}