#include <bits/stdc++.h>
using namespace std;

const int nmax = 200002;
const int mmax = 400004;
const int inf = (1<<30);

vector <int> v[nmax], w[nmax];
int n, m, x, y, z;
int parent[nmax], key[nmax];
int parent_weight[nmax];

set <pair <int, int>> Q;
bool inQ[nmax];

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");

    f>>n>>m;
    for(int i=1; i<=m; i++) {
        f>>x>>y>>z;
        v[x].push_back(y);
        v[y].push_back(x);

        w[x].push_back(z);
        w[y].push_back(z);
    }

    for(int i=1; i<=n; i++)
        parent[i] = -1,
        key[i] = inf;
    key[1] = 0;     // start building the MST from 1

    for(int i=1; i<=n; i++) {
        Q.insert(make_pair(key[i], i));
        inQ[i] = true;
    }

    while(!Q.empty()) {
        auto t = Q.begin();
        Q.erase(Q.begin());

        x = t->second; // add this vertex to the MST
        inQ[x] = false;

        for(int i=0; i<int(v[x].size()); i++) {
            int y = v[x][i];
            int weight = w[x][i];

            if(inQ[y] && weight < key[y]) {
                Q.erase(Q.find(make_pair(key[y], y)));
                key[y] = weight;
                Q.insert(make_pair(key[y], y));
                parent[y] = x;
                parent_weight[y] = weight;
            }
        }
    }

    int total_weight = 0;
    for(int i=2; i<=n; i++)
        total_weight += parent_weight[i];

    g<<total_weight<<"\n"<<n-1<<"\n";
    for(int i=2; i<=n; i++)
        g<<i<<" "<<parent[i]<<"\n";

    return 0;
}