# include <algorithm>
# include <cstdio>
# include <vector>
using namespace std;

# define x first
# define y second

const char *FIN = "apm.in", *FOU = "apm.out";
const int MAX = 400005;

int N, M, solution, T[MAX];
pair <int, pair <int, int> > P[MAX];
vector <int> SOL;

int search (int x) {
    if (x != T[x]) T[x] = search (T[x]);
    return T[x];
}

void reunion (int x, int y) {
    T[search (x)] = search (y);
}

int sol = 0, total;
int comp (void) {
    return ++sol;
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
        scanf ("%d %d %d", &P[i].y.x, &P[i].y.y, &P[i].x);
    generate_n (T + 1, N, comp);
    sort (P + 1, P + M + 1);
    for (int i = 1; i <= M; ++i) {
        if (search (P[i].y.x) != search (P[i].y.y)) {
            solution += P[i].x, reunion (P[i].y.x, P[i].y.y), total += 1;
            SOL.push_back (i);
        }
    }
    if (total == M) return -1;
    printf ("%d\n%d\n", solution, N - 1);
    for (int i = 0; i < N - 1; ++i)
        printf ("%d %d\n", P[SOL[i]].y.x, P[SOL[i]].y.y);
}