#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

#define NMAX 200002
#define INF 200000200

vector < pair<int,int> > Graf[NMAX], VANS;
int N, M, L, cost;
int D[NMAX], Heap[NMAX * 2 + 100], Poz[NMAX], Tata[NMAX];

void introduce_in_apm(int x) {
    for(unsigned int i = 0;i < Graf[x].size(); ++i)
    {
        int nod = Graf[x][i].first;
        int cost = Graf[x][i].second;
        D[nod] = min(D[nod],cost);
        if (D[nod] == cost) Tata[nod] = x;
    }
}

void push(int k) {  ///sift
    while( (k * 2 <= L && D[Heap[k]] > D[Heap[k * 2]]) || (k * 2 + 1 <= L && D[Heap[k]] > D[Heap[k * 2 +1 ]]) )
    {
        if (D[Heap[k * 2]] < D[Heap[k * 2 + 1]] || k * 2 + 1 > L)
        {
            swap(Heap[k],Heap[k * 2]);
            swap(Poz[Heap[k]],Poz[Heap[k * 2]]);
            k *= 2;
        }
        else
        {
            swap(Heap[k],Heap[k * 2 + 1]);
            swap(Poz[Heap[k]],Poz[Heap[k * 2 + 1]]);
            k = k * 2 + 1;
        }
    }
}

void pop(int k) {  ///percolate
    while(k > 1 && D[Heap[k]] < D[Heap[k / 2]])
    {
        swap(Heap[k], Heap[k / 2]);
        swap(Poz[Heap[k]], Poz[Heap[k / 2]]);
        k = k / 2;
    }
}

void introduce_in_heap(int nod)
{
    Heap[++L] = nod;
    Poz[nod] = L;
    pop(L);
}

int scoate_radacina_heap()
{
    int x = Heap[1];
    swap(Heap[1],Heap[L]);
    swap(Poz[Heap[1]],Poz[Heap[L]]);
    L--;
    push(1);
    Poz[x] = 0;
    return x;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    f>>N>>M;

    int i, x, y, c;

    for(i = 1; i <= M; i++) {
        f>>x>>y>>c;
        Graf[x].push_back(make_pair(y, c));
        Graf[y].push_back(make_pair(x, c));
    }

    for(i = 1; i <= N; i++) D[i] = INF;
    D[1] = 0;
    introduce_in_apm(1);
    for(i = 2; i <= N; i++)
        introduce_in_heap(i);

    for(int i = 1;i < N; ++i)
    {
        int x = scoate_radacina_heap();
        introduce_in_apm(x);
        cost += D[x];
        VANS.push_back(make_pair(x, Tata[x]));
        for(unsigned int j = 0;j < Graf[x].size(); ++j)
        {
            int nod = Graf[x][j].first;
            if (Poz[nod]) pop(Poz[nod]);
        }
    }

    printf("%d\n",cost);
    printf("%d\n",N-1);
    for(unsigned int i = 0;i < N - 1; ++i)
        printf("%d %d\n",VANS[i].second,VANS[i].first);
    return 0;
}