#include <bits/stdc++.h>

using namespace std;

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

struct edge{int x, y, c;};
struct cmp{
    bool operator()(const edge &x, const edge &y){
        return x.c>y.c;
    }
};
const int nmax = 200005, f_mare = 2000000000;
vector <edge> ls[nmax];
priority_queue <edge, vector<edge>, cmp> q;
int cs[nmax], lft[nmax], rgt[nmax], nr, ct, l;
bool viz[nmax];
int n, m, x, y, c, i, j;

int main() {
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;
        ls[x].push_back({x,y,c});
        ls[y].push_back({y,x,c});
    }
    q.push({0,1,0});
    for (i = 2; i <= n; i++)
        cs[i] = f_mare;

    while(!q.empty()) {
        x = q.top().x;
        y = q.top().y;
        c = q.top().c;
        q.pop();
        if (y!=1&&viz[y]==0) {
            viz[y]=1;
            ct += c;
            lft[++nr] = x;
            rgt[nr] = y;
        }
        x = y;
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            y = ls[x][i].y;
            c = ls[x][i].c;
            if (cs[y] > c && viz[y] == 0) {
                cs[y] = c;
                q.push({x,y,c});
            }
        }
    }
    g << ct << '\n' << n-1 << '\n';
    for (i = 1; i < n; i++)
        g << lft[i] << ' ' << rgt[i] << '\n';
    return 0;
}