#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 peaks, arches, totalCost;
int isInResult[MAX_SIZE];
vector<pair<int, int>> graph[MAX_SIZE], result;
priority_queue<pair<int, pair<int, int>>> positions; // priority queue in functie de cost

void findMinimumCosts() {
    positions.push(make_pair(0, make_pair(0, 1))); // cost,parent,node
    while (!positions.empty()) {
        int cost = -positions.top().first;
        int parent = positions.top().second.first;
        int currentNode = positions.top().second.second;
        positions.pop();
        if (isInResult[currentNode] == 0) {
            isInResult[currentNode] = 1;
            totalCost += cost;
            if (currentNode != 1) {
                result.push_back(make_pair(parent, currentNode));
            }
            for (pair<int, int> element : graph[currentNode]) {
                int nextNode = element.second;
                int nextCost = element.first;
                if (isInResult[nextNode] == 0) {
                    positions.push(make_pair(-nextCost, make_pair(currentNode, nextNode)));
                }
            }
        }
    }
}

int main() {
    fin >> peaks >> arches;
    for (int i = 1; i <= arches; ++i) {
        int start, end, cost;
        fin >> start >> end >> cost;
        graph[start].push_back(make_pair(cost, end));
        graph[end].push_back(make_pair(cost, start));
    }
    findMinimumCosts();
    fout << totalCost << "\n" << result.size() << "\n";
    for (pair<int, int> element : result) {
        fout << element.first << ' ' << element.second << "\n";
    }
    return 0;
}