#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

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

const int MAX_SIZE = 200005;

int n, m, totalCost;
vector<pair<int, int>> graph[MAX_SIZE];
bitset<MAX_SIZE> inSolution;
priority_queue<pair<int, pair<int, int>>> c;
vector<pair<int, int>> result;

void prim() { // algoritmul lui Prim
    c.push(make_pair(0, make_pair(1, 0)));
    while (!c.empty()) {
        int cost = c.top().first;
        int i = c.top().second.first;
        int tata = c.top().second.second;
        c.pop();
        if (!inSolution[i]) {
            inSolution[i] = true;
            totalCost += cost;
            if (tata != 0) {
                result.push_back(make_pair(i, tata));
            }
            for (pair<int, int> way : graph[i]) {
                if (!inSolution[way.first]) {
                    c.push(make_pair(-way.second, make_pair(way.first, i)));
                }
            }
        }
    }
}
 
int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    prim();
    fout << totalCost << '\n' << result.size() << '\n';
    for (pair<int, int> p : result) {
        fout << p.first << ' ' << p.second << '\n';
    }
    return 0;
}