#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

#define MAXN 200000

FILE *fin = fopen("apm.in", "r");
FILE *fout = fopen("apm.out", "w");

std::vector <std::pair<int, int>> v[MAXN + 1];
int min[MAXN + 1];
int e[MAXN + 1];
int t[MAXN + 1];
bool viz[MAXN + 1];
std::multiset <std::pair<int, int>> s;

int main()
{
    int n, m, x, y, c;
    long long cost = 0;
    fscanf(fin, "%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        fscanf(fin, "%d%d%d", &x, &y , &c);
        v[x].push_back(std::make_pair(y, c));
        v[y].push_back(std::make_pair(x, c));
    }
    int siz = v[1].size();
    for (int i = 0; i < siz; i++) {
        y = v[1][i].first;
        c = v[1][i].second;
        min[y] = c;
        e[y] = 1;
        s.insert(std::make_pair(c, y));
    }
    viz[1] = 1;
    for (int i = 2; i <= n; i++) {
        c = s.begin()->first;
        y = s.begin()->second;
        cost += c;
        s.erase(s.begin());
        t[y] = e[y];
        viz[y] = 1;
        siz = v[y].size();
        for (int j = 0; j < siz; j++) {
            int a = v[y][j].first;
            int b = v[y][j].second;
            if (viz[a] == 0) {
                if (min[a] > b && e[a] > 0) {
                    min[a] = b;
                    e[a] = y;
                    s.insert(std::make_pair(min[a], a));
                }
                else if (e[a] == 0) {
                    min[a] = b;
                    e[a] = y;
                    s.insert(std::make_pair(min[a], a));
                }
            }
        }
    }
    fprintf(fout, "%lld\n%d\n", cost, n - 1);
    for (int i = 1; i <= n; i++) {
        if (t[i] != 0)
            fprintf(fout, "%d %d\n", i, t[i]);
    }
    return 0;
}