#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5 + 5;
vector < pair <int, int> > g[NMAX]; //  node, cost
bitset <NMAX> chosen;

int main()
{
    int n, m, i, j;

    fin >> n >> m;
    for(i = 1; i <= m; ++i){
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    priority_queue < pair <int, pair <int, int>>, vector <pair <int, pair <int, int> > >, greater < pair <int, pair <int, int>> >> heap; // cost, {node, prev node}
    heap.push({0, {1, 0}});

    int ans = 0;
    vector < pair <int, int> > tree;
    while(!heap.empty()){
        int currentCost = heap.top().first;
        int currentNode = heap.top().second.first;
        int prevNode = heap.top().second.second;
        heap.pop();

        if(chosen[currentNode]) continue;

        ans += currentCost;
        chosen[currentNode] = 1;
        tree.push_back({currentNode, prevNode});
        for(auto &it: g[currentNode])
            if(!chosen[it.first])
                heap.push({it.second, {it.first, currentNode}});

    }

    fout << ans << '\n' << tree.size() - 1 << '\n';

    for(i = 1; i < tree.size(); ++i)
        fout << tree[i].first << ' ' << tree[i].second << '\n';

    return 0;
}