#include <bits/stdc++.h>

using namespace std;

int n, m, suma;
int indice[400005]; /// indice[i] = cea mai mica i muchie
int X[400005], Y[400005], Cost[400005]; ///X - inceputul muchiei, y - sfarsitul muchiei, Cost = costul muchiei
int grupa[400005]; /// subarborele in care se afla muchia i
vector <int> answer;

int radacina(int x)
{
    int root, aux_variable;
    for (root = x; root != grupa[root]; root = grupa[root]);
    for (; x != root;)
    {
        aux_variable = grupa[x];
        grupa[x] = root;
        x = aux_variable;
    }
    return root;
}

void reuniune(int a, int b)
{
    a = radacina(a);
    b = radacina(b);
    grupa[b] = a;
}

bool cmp(int a, int b)
{
    return Cost[a] < Cost[b];
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d %d %d", &X[i], &Y[i], &Cost[i]),
        indice[i] = i;
    for (int i = 1; i <= n; i++)
        grupa[i] = i;
    sort(indice + 1, indice + 1 + m, cmp);
    for (int i = 1, nrfin = 1; i <= m && nrfin <= n - 1; i++)
        if (radacina(X[indice[i]]) != radacina(Y[indice[i]]))
        {
            nrfin++;
            suma += Cost[indice[i]];
            answer.push_back(indice[i]);
            reuniune(X[indice[i]], Y[indice[i]]);
        }

    printf("%d\n%d\n", suma, n - 1);
    for (const auto &it : answer)
        printf("%d %d\n", Y[it], X[it]);
    return 0;
}