/**
  *  Worg
  */
#include <queue>
#include <cstdio>
#include <vector>

#define pb      push_back

using namespace std;
FILE *fin = freopen("apm.in", "r", stdin);
FILE *fout = freopen("apm.out", "w", stdout);

const int MAX_N = 1 + 200000,
          MAX_M = 1 + 400000;

struct neighbour {

    int vertex, cost;

    neighbour(int vertex, int cost) {

        this->vertex = vertex;
        this->cost = cost;
    }
};

struct edge {

    int a, b, cost;

    edge(int a, int b, int cost) {

        this->a = a;
        this->b = b;
        this->cost = cost;
    }

    bool operator <(const edge &other) const {

        return this->cost > other.cost;
    }
};

priority_queue < edge > candidates;
vector < neighbour > G[MAX_N];
vector < edge > sol;
bool solved[MAX_N];

int m, n, solCost;

void readData() {

    scanf("%d %d ", &n, &m);

    for(int i = 1; i <= m; ++i) {

        int x, y, cost;
        scanf("%d %d %d ", &x, &y, &cost);
        G[x].pb(neighbour(y, cost));
        G[y].pb(neighbour(x, cost));
    }
}

void init() {

    solved[1] = true;

    for(vector < neighbour >::iterator it = G[1].begin(); it != G[1].end(); ++it)
        candidates.push(edge(1, it->vertex, it->cost));
}

void solve() {

    while(!candidates.empty()) {

        edge Edge = candidates.top();
        candidates.pop();

        if(!(solved[Edge.a] && solved[Edge.b])) {

            sol.pb(Edge);
            solCost += Edge.cost;

            int newNode = (solved[Edge.a] == true) ? Edge.b : Edge.a;
            for(vector < neighbour >::iterator it = G[newNode].begin(); it != G[newNode].end(); ++it)
                if(!solved[it->vertex])
                    candidates.push(edge(newNode, it->vertex, it->cost));
            solved[newNode] = true;
        }
    }
}

void writeData() {

    printf("%d\n%d\n", solCost, sol.size());
    for(vector < edge >::iterator it = sol.begin(); it != sol.end(); ++it)
        printf("%d %d\n", it->a, it->b);
}

int main() {

    readData();
    init();
    solve();
    writeData();
    return 0;
}