#include <fstream>
#include <algorithm>
#include <vector>
#define MAXN 200000
#define MAXM 400000
using namespace std;

struct edge{
    int x, y, c;
};
typedef vector <int> list;
edge edges[MAXM + 1];
int dad[MAXN + 1];
list apm;

bool cmp(edge a, edge b) {
    return a.c < b.c;
}

int find(int node) {
    while (node != dad[node])
        node = dad[node];
    return node;
}

void connect(int n1, int n2) {
    int d2 = find(n2);
    while (n1 != dad[n1]) {
        int aux = dad[n1];
        dad[n1] = d2;
        n1 = aux;
    }
    dad[n1] = d2;
}

inline bool conex(int n1, int n2) {
    return (find(n1) == find(n2));
}

int main () {
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < m ; ++i)
        cin >> edges[i].x >> edges[i].y >> edges[i].c;

    sort(edges, edges + m, cmp);
    for (int i = 1 ; i <= n ; ++i)
        dad[i] = i;

    int minc = 0;
    for (int i = 0 ; i < m ; ++i)
        if (!conex(edges[i].x, edges[i].y)) {
            apm.push_back(i);
            minc += edges[i].c;
            connect(edges[i].x, edges[i].y);
        }

    cout << minc << "\n" << n - 1 << "\n";
    for (int i = 0 ; i < n - 1 ; ++i)
        cout << edges[apm[i]].x << " " << edges[apm[i]].y << "\n";

    return 0;
}