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

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

vector <pair <int, int>> v[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<=n; i++)
        v[i].reserve(10);
    for(int i=1; i<=m; i++) {
        f>>x>>y>>z;
        v[x].push_back(make_pair(y, z));
        v[y].push_back(make_pair(x, z));
    }

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

    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].first;
            int weight = v[x][i].second;

            if(inQ[y] && weight < key[y]) {
                auto tmp = Q.find(make_pair(key[y], y));
                if(tmp != Q.end())
                    Q.erase(tmp);

                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;
}