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

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

void Prim(vector<vector<pair<int,int>>> adj, int n){
    priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> pq;

    vector<bool> visited(n+1, false);

    vector<pair<int,int>> mst_edges;
    int cost_total = 0;
    int muchii_selectate = 0;

    pq.push({0, {1,-1}});

    while (pq.size() > 0 ){
        auto top = pq.top();

        pq.pop();

        int cost_m = top.first;
        int curr = top.second.first;
        int prev = top.second.second;

        if(visited[curr] == 1)
            continue;

        visited[curr] = 1;    

        if (prev != -1){ // nu e radacina
            mst_edges.push_back({curr, prev});
            muchii_selectate++;
            cost_total += cost_m;
        }

        for (auto vecin : adj[curr]){
            int v = vecin.first;
            int c = vecin.second;

            if(!visited[v]){
                pq.push({c,{v, curr}});
            }
        }

    }

    fout << cost_total << "\n" << muchii_selectate << "\n";

    for (auto a : mst_edges){
        fout << a.first << " " << a.second << "\n";
    }




}


int main(){
    int n, m;
    fin >> n >> m;
    int u, v, cost;

    vector<vector<pair<int,int>>> adj(n+1);

    for (int i = 0 ; i < m ; i++){
        fin >> u >> v >> cost;
        adj[u].push_back({v,cost});
        adj[v].push_back({u,cost});
    }

    Prim(adj, n);
}