#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <utility>

using namespace std;

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

vector<pair<int,int>> L[200001];
priority_queue<pair<int,int>> pq;

int viz[200001], p[200001], d[200001];

int main(){
    int n, m;
    fin >> n >> m;

    for (int i=1; i<=m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        L[y].push_back({x,c});
        L[x].push_back({y,c});
    }

    for (int i=1; i<=n; i++){
        d[i] = INT_MAX;
    }
    d[1] = 0;

    int sol = 0;
    vector<pair<int,int>> muchii_sol;
    pq.push({-d[1],1});

    while (pq.size() > 0){
        int cost = -pq.top().first;
        int nod = pq.top().second;
        pq.pop();
        if (viz[nod] == 1)
            continue;
        viz[nod] = 1;
        sol += cost;
        if (p[nod] != 0)
            muchii_sol.push_back({nod, p[nod]});
        
        for (auto& x : L[nod]){
            if (d[x.first] > x.second){
                d[x.first] = x.second;
                pq.push({-d[x.first], x.first});
                p[x.first] = nod;
            }
        }
    }

    fout << sol << "\n";
    fout << muchii_sol.size() << "\n";

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

    return 0;



}