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

using namespace std;

const int NMAX = 2e5+1;
const int INF = 2e8+1;

vector <pair<int, int>> s[NMAX];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> h;
int d[NMAX];
bool in_t[NMAX];
int pred[NMAX];

int prim(int n){
    int cost_total = 0;
    for(int i = 2; i <= n; i++){
        d[i] = INF;
    }
    d[1] = 0;
    h.push({0, 1});
    while(!h.empty()){
        int x = h.top().second;
        h.pop();
        if(in_t[x]){
            continue;
        }
        cost_total += d[x];
        in_t[x] = true;
        for(auto i: s[x]){
            int cost = i.first;
            int y = i.second;
            if(!in_t[y] && cost < d[y]){
                d[y] = cost;
                h.push({cost, y});
                pred[y] = x;
            }
        }
    }
    return cost_total;
}

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

    int n, m;
    fin >> n >> m;

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

    fout << prim(n) << "\n" << n - 1 << "\n";

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

    fin.close();
    fout.close();
    return 0;
}