#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

int main(){
    int x, y, z, w, n, m, v, vw;
    fin >> n >> m;
    vector< vector< pair<int, int> > > g(n+1);
    vector<int> best(n+1, -1);
    vector<char> used(n+1, false);
    vector<int> tata(n+1, -1);
    

    

    for(int i = 0; i < m; i++){
        fin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    priority_queue< pair<int, int>, vector< pair<int, int>>, greater< pair<int, int> > > pq;

    //prim
    pq.push({0, 1});
    best[1] = 0;


    int taken = -1;
    long long total = 0;

    while(!pq.empty()){
        w = pq.top().first;
        x = pq.top().second;
        pq.pop();

        if(used[x]) continue;
        if(best[x] != w) continue;

        used[x] = true;
        total += w;
        taken++;

        for(const auto& [v,vw] : g[x]){
            if(used[v]) continue;

            if(best[v] == -1 || vw < best[v]){
                best[v] = vw;
                tata[v] = x;
                pq.push({vw, v});
            }
        }

    }

    fout << total << endl;
    fout << taken << endl;


    for(int i = 2; i <= n; i++){
        fout << i << " " << tata[i] << endl;
    }

    return 0;
}