#include<bits/stdc++.h>

using namespace std;

int N, M, col[200009], mi[200009], x[400009], y[400009], z[400009];
bool ap[400009];
long long ans;
vector < int > v[200009];

bool addEdge (int i)
{
    if (i == -1 || ap[i] == 1) return 0;
    v[x[i]].push_back (y[i]);
    v[y[i]].push_back (x[i]);
    ap[i] = 1; ans += z[i]; return 1;
}

void dfs (int nod, int c)
{
    col[nod] = c;
    for (auto it : v[nod])
        if (col[it] == 0)
            dfs (it, c);
}

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], &z[i]), col[i] = i;
bool ok = 1;
while (ok)
{
    for (int i=1; i<=N; i++)
        mi[i] = -1;
    for (int i=1; i<=M; i++)
    if (col[x[i]] != col[y[i]])
    {
        int a = col[x[i]], b = col[y[i]];
        if (mi[a] == -1 || z[mi[a]] > z[i])
            mi[a] = i;
        if (mi[b] == -1 || z[mi[b]] > z[i])
            mi[b] = i;
    }
    ok = 0;
    for (int i=1; i<=N; i++)
        ok |= addEdge (mi[i]), col[i] = 0;
    int nr = 0;
    for (int i=1; i<=N; i++)
        if (col[i] == 0)
            dfs (i, ++nr);
}
printf ("%lld\n%d\n", ans, N - 1);
for (int i=1; i<=M; i++)
    if (ap[i])
        printf ("%d %d\n", x[i], y[i]);
return 0;
}