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

using namespace std;

const int maxn = 200005;
const int inf = 0x3f3f3f3f;
typedef int Heap;
Heap H[2 * maxn + 100];
int VEC[maxn], ans, V[maxn], POZ[maxn];
int N, M, L;
vector < pair <int, int> > G[maxn], ARB;

void Insert_in_Apm(int k)
{
    for (int i = 0; i < G[k].size(); ++i)
    {
        int node = G[k][i].first;
        int cost = G[k][i].second;
        V[node] = min(V[node], cost);
        if (V[node] == cost) VEC[node] = k;
    }
}

void Sift(int k)
{
    int son;
    do
    {
        son = 0;
        if ((k << 1) <= L)
        {
            son = (k << 1);
            if ((k << 1) + 1 <= L && V[H[(k << 1) + 1]] < V[H[(1 << k)]])
                son = (1 << k) + 1;
            if (V[H[son]] > V[H[k]])
                son = 0;
        }
        if (son)
        {
            swap(H[son], H[k]);
            swap(POZ[H[son]], POZ[H[k]]);
            k = son;
        }
    } while (son);
}

void Percolate(int k)
{
    while (k > 1 && V[H[k]] < V[H[k >> 1]])
    {
        swap(H[k], H[k >> 1]);
        swap(POZ[H[k]], POZ[H[k >> 1]]);
        k >>= 1;
    }
}

void Insert_in_Heap(int k)
{
    ++L;
    H[L] = k;
    POZ[k] = L;
    Percolate(L);
}

int Root()
{
    int R = H[1];
    swap(H[1], H[L]);
    swap(POZ[H[1]], POZ[H[L]]);
    --L;
    Sift(1);
    POZ[R] = 0;
    return R;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G[a].push_back(make_pair(b, c));
        G[b].push_back(make_pair(a, c));
    }
    for (int i = 1; i <= N; ++i)
        V[i] = inf;
    V[1] = 0;
    Insert_in_Apm(1);
    for (int i = 2; i <= N; ++i)
        Insert_in_Heap(i);
    for (int i = 1; i < N; ++i)
    {
        int R = Root();
        Insert_in_Apm(R);
        ans += V[R];
        ARB.push_back(make_pair(R, VEC[R]));
        for (int j = 0; j < G[R].size(); ++j)
		{
			int node = G[R][j].first;
			if (POZ[node]) Percolate(POZ[node]);
		}
    }
    printf("%d\n", ans);
    printf("%d\n", N - 1);
    for (int i = 0; i < N - 1; ++i)
        printf("%d %d\n", ARB[i].first, ARB[i].second);
    return 0;
}