#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 poz)
{
    while ((poz * 2 <= L && V[H[poz]] > V[H[poz * 2]]) || (poz * 2 + 1 <= L && V[H[poz]] > V[H[poz * 2 + 1]]))
    {
        if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)
        {
            swap(H[poz],H[poz * 2]);
            swap(POZ[H[poz]],POZ[H[poz * 2]]);
            poz *= 2;
        }
        else
        {
            swap(H[poz],H[poz * 2 + 1]);
            swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);
            poz = poz * 2 + 1;
        }
    }
}

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

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;
}

void Update_Heap(int node)
{
    for (int i = 0; i < G[node].size(); ++i)
    {
        int k = G[node][i].first;
        if (POZ[k])
            Percolate(POZ[k]);
    }
}

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]));
        Update_Heap(R);
    }
    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;
}