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

using namespace std;

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

vector<pair<int, int>> g[200005];
int n, m, isArbore[200005];

int main() {
    fin >> n >> m;
    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({ y, c });
        g[y].push_back({ x, c });
    }

    priority_queue<pair<int, pair<int, int>>> pq;
    vector<pair<int, int>> ans;
    int costTotal = 0;
    for (auto adjacent1 : g[1]) pq.push({ -adjacent1.second, {1, adjacent1.first} });
    isArbore[1] = 1; 

    while (!pq.empty()) {
        int parinte = pq.top().second.first;
        int copil = pq.top().second.second;
        int cost = -pq.top().first;
        pq.pop();

        if (isArbore[copil]) continue;
        isArbore[copil] = 1;
        ans.push_back({ parinte, copil });
        costTotal += cost;

        for (auto adjCopil : g[copil]) {
            if (!isArbore[adjCopil.first]) {
                pq.push({ -adjCopil.second, {copil, adjCopil.first} });
            }
        }
    }
    fout << costTotal << '\n' << ans.size() << '\n';
    for (auto p : ans) fout << p.first << ' ' << p.second << '\n';
}