#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#define son first.first
#define son2 first.second
#define cost second
using namespace std;

typedef pair <int, int> edge;
typedef pair <pair <int, int>, int> dedge;
const int NMAX = 102;

struct predicate {

    inline bool operator () (const dedge &a, const dedge &b) {

        return a.cost > b.cost;

    }

};

priority_queue <dedge, vector<dedge>, predicate> Q;
vector <edge> G[NMAX];
vector <edge> edges;
bitset <NMAX> check;
int father[NMAX];

int main () {

    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    dedge node;
    vector <edge> :: iterator k;
    int N, M, i, a, b, c, cost = 0;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i) {
        scanf ("%d%d%d", &a, &b, &c);
        G[a].push_back (make_pair (b, c));
        G[b].push_back (make_pair (a, c));
    }
    check[1] = 1;
    for (k = G[1].begin (); k != G[1].end (); ++k) {
        Q.push (make_pair (make_pair (1, k->first), k->second));
    }
    while (!Q.empty ()) {
        node = Q.top ();
        Q.pop ();
        if (!check[node.son2]) {
        edges.push_back (make_pair (node.son, node.son2));
        cost += node.cost;
        check[node.son2] = 1;
        for (k = G[node.son2].begin (); k != G[node.son2].end (); ++k)
            if (!check[k->first]) {
                Q.push (make_pair (make_pair (node.son2, k->first), k->second));
            }
        }
    }
    printf ("%d\n%d\n", cost, N - 1);
    for (i = 0; i < N - 1; ++i)
        printf ("%d %d\n", edges[i].first, edges[i].second);
}