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

using namespace std;

#define FIN "apm.in"
#define FOUT "apm.out"

#define N 200002

int n, m, end, cost;
int h[N], p[N], d[N], pr[N], a[N];

vector < pair <int, int> > v[N];

void swap(int a, int b, int V[])
{
    int aux;

    aux = V[a];

    V[a] = V[b];

    V[b] = aux;
}

void down_heap(int i, int n)
{
	int j = i;

	if (2 * i <= n && d[h[j]] > d[h[2 * i]])
		j = 2 * i;

    if (2 * i + 1 <= n && d[h[j]] > d[h[2 * i + 1]])
		j = 2 * i + 1;

	if (i != j)
	{
        swap(h[i], h[j], p);
        swap(i, j, h);

		down_heap(j, n);
	}
}

void up_heap(int i, int n)
{
    if (i > 1 && d[h[i]] < d[h[i / 2]])
    {
        swap(h[i], h[i / 2], p);
        swap(i, i / 2, h);

        up_heap(i / 2, n);
    }
}

void solve()
{
    int i, x, j = 0;

    h[end = 1] = 1;

    a[1] = p[1] = 1;

    while (end)
    {
        x = h[1];

        a[++ j] = x;

        if (j > 1)
            cost += d[x];

        for (i = 0; i < v[x].size(); ++ i)
        {
            if (p[v[x][i].first] && p[v[x][i].first] != N && d[v[x][i].first] > v[x][i].second)
            {
                pr[v[x][i].first] = x;

                d[v[x][i].first] = v[x][i].second;

                up_heap(p[v[x][i].first], end);
                down_heap(p[v[x][i].first], end);
            }
            else if (!p[v[x][i].first])
            {
                pr[v[x][i].first] = x;

                d[v[x][i].first] = v[x][i].second;

                h[++ end] = v[x][i].first;

                p[v[x][i].first] = end;

                up_heap(end, end);
            }
        }

        p[h[end]] = p[x];

        swap(p[x], end, h);

        -- end;

        down_heap(p[x], end);
        up_heap(p[x], end);

        p[x] = N;

    }
}

int main()
{
    int i, x, y, c;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d", &n, &m);

    for (i = 1; i <= m; ++ i)
    {
        scanf("%d%d%d", &x, &y, &c);

        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }

    solve();

    printf("%d\n%d\n", cost, n - 1);

    for (i = 2; i <= n; ++ i)
        printf("%d %d\n", pr[a[i]], a[i]);
}