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


using namespace std;

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

const int nmax = 400005;
struct edge {
    int x, y, c;
};

struct cmp {
    bool operator()(const edge &a, const edge &b) {
        return a.c > b.c;
    }
};

edge sol[2*nmax];
priority_queue<edge, vector<edge>, cmp> top;
vector<edge> ls[nmax];
int n, m, x, y, c, i, yy, viz[nmax], cst[nmax], N;
long long sm;

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});
    }
    for (i = 2; i <= n; i++)
        cst[i] = 10000;

    viz[1] = 1;
    top.push({0,1,0});
    while (top.empty() == 0) {
        x = top.top().x;
        y = top.top().y;
        c = top.top().c;
        top.pop();
        if (y != 1 && viz[y] == 0) {
            viz[y] = 1;
            sol[++N] = {x,y,100};
            sm += c;
        }

        for (auto z : ls[y]) {
            yy = z.y;
            c = z.c;
            if (viz[yy] == 0 && cst[yy] > c) {
                cst[yy] = c;
                top.push({y,yy,c});
            }
        }
    }
    g << sm << '\n' << N << '\n';
    for (i = 1; i <= N; i++)
        g << sol[i].x << ' ' << sol[i].y << '\n';
}