#include <iostream>
#include <queue>
#include <vector>

#define NMAX 200005

using namespace std;

typedef pair<int, int> pii;

struct elem {
    int x, y, z; //de la, spre, lungime

    inline bool operator < (const elem &X) const {
        return z > X.z;
    }
};

int n, m, ans[NMAX];
bool v[NMAX];
vector<pii> adj[NMAX];
priority_queue<elem> pq;

int algPrim() {
    int sum = 0;
    pq.push({0, 1, 0});
    while(!pq.empty()) {
        const elem crt = pq.top();
        pq.pop();

        if(v[crt.y]) continue;

        sum += crt.z;
        v[crt.y] = 1;
        ans[crt.y] = crt.x;

        for(const auto &el : adj[crt.y])
            if(!v[el.first])
                pq.push({crt.y, el.first, el.second});
    }
    return sum;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int x, y, z; m; --m) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }
    printf("%d\n", algPrim());
    printf("%d\n", n - 1); //arborele are n - 1 noduri
    for(int i = 2; i <= n; ++i) {
        printf("%d %d\n", i, ans[i]);
    }
    return 0;
}