#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>>> positions; // priority queue in functie de cost
vector<pair<int, int>> result;

void prim() { // algoritmul lui Prim
    positions.push(make_pair(0, make_pair(1, 0))); // pornim de la 1, neavand parinte
    while (!positions.empty()) {
        int cost = -positions.top().first; // opusul
        int currentNode = positions.top().second.first;
        int parent = positions.top().second.second;
        positions.pop();
        if (!inSolution[currentNode]) { // daca nu e in solutie
            inSolution[currentNode] = true; // il bagam in solutie
            if (currentNode != 1) {
                result.push_back(make_pair(currentNode, parent)); //adaugam muchia in rezultat
                totalCost += cost; //costul se mareste
            }
            for (pair<int, int> way : graph[currentNode]) { // iteram copiii nodului curent
                int nextElement = way.first;
                int cost = way.second;
                if (!inSolution[nextElement]) { // daca nu e in solutie deja
                    positions.push(make_pair(-cost, make_pair(nextElement, currentNode))); // il adaugam in solutie, tatal lui fiind nodul curent
                }
            }
        }
    }
}
 
int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int start, end, cost;
        fin >> start >> end >> cost;
        graph[start].push_back(make_pair(end, cost));
        graph[end].push_back(make_pair(start, cost));
    }
    prim();
    fout << totalCost << '\n' << result.size() << '\n';
    for (pair<int, int> p : result) {
        fout << p.first << ' ' << p.second << '\n';
    }
    return 0;
}