#include <bits/stdc++.h>

using namespace std;

struct muchie
{
    int x, y, cost;
};

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

muchie lista_m[400005];

int n, m, ct, k, x, y;
int Lista[400005];

int main()
{
    freopen("kruskal.in", "r", stdin);
    freopen("kruskal.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1, c; i <= m; i++)
        scanf("%d %d %d", &x, &y, &c), lista_m[i].x = x, lista_m[i].y = y, lista_m[i].cost = c;
    for (int i = 1; i <= n; i++)
        Lista[i] = i;
    sort(lista_m + 1, lista_m + m + 1, cmp);
    for (int i = 1; k < n - 1; i++)
        if (Lista[lista_m[i].x] != Lista[lista_m[i].y])
        {
            k++;
            ct += lista_m[i].cost;
            x = Lista[lista_m[i].y];
            y = Lista[lista_m[i].x];
            for (int i1 = 1; i1 <= n; i1++) if (Lista[i1] == x) Lista[i1] = y;
        }
    printf("%d\n%d\n", ct, n - 1);
    for (int i = 1; i <= n - 1; i++)
        printf("%d %d\n", lista_m[i].y, lista_m[i].x);
    return 0;
}