//#include <iostream>
#include <vector>
#include <list>
#include <fstream>
#include <set>
#define INF 0x3f3f3f3f
using namespace std;
vector<list< pair<int, int> > > V;
vector<int> d, pred, viz;
set<pair<int, int> > Q;
int n, m, x, y, c, st;
ifstream in("apm.in");
ofstream cout("apm.out");
long long cost_total=0;
int main() {
    in >> n >> m;
    V.resize(n+1);

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

    }
    d.resize(n+1, INF);
    pred.resize(n+1);
    viz.resize(n+1);
    pred[1] = 1;
    d[1] = 0;
    Q.insert({d[1], 1});
    while(!Q.empty()){
        int K = Q.begin()->second;
        Q.erase(Q.begin());

        if(!viz[K]) {
            viz[K] = 1;
            cost_total+=d[K];

            for (auto p : V[K]) {
                if (!viz[p.second]) {
                    if (d[p.second] > p.first) {
                        d[p.second] = p.first;
                        Q.insert({p.first, p.second});
                        pred[p.second] = K;
                    }
                }
            }
        }
    }
    cout << cost_total << '\n';
    cout << n-1 << '\n';
    for(int i=1;i<=n;i++)
        if(i!=pred[i]) cout << pred[i] << ' ' << i << endl;
    return 0;
}