#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define iter vector<pair<int, int> > :: iterator
const char iname[] = "apm.in";
const char oname[] = "apm.out";
const int MAXM = 400000;
const int MAXN = 200000;
const int INF = 1 << 30;
int N, M, L, cost_total;
int H[MAXN], POZ[MAXN], TATA[MAXN], COST[MAXN];
vector < pair<int, int> > graf[MAXN], apm;
void insert_apm(int nod)
{
    for(iter it = graf[nod].begin(); it != graf[nod].end(); ++it)
    {
        int nod2 = it -> first;
        int cost = it -> second;
        COST[nod2] = min(COST[nod2], cost);
        if(COST[nod2] == cost) TATA[nod2] = nod;
    }
}

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

void downheap(int poz)
{
    while((poz*2 + 1 <= L && COST[H[poz]] > COST[H[poz*2+1]])||(poz*2 <= L && COST[H[poz]] > COST[H[poz*2]]))
    {
        if(COST[H[poz*2+1]] > COST[H[poz*2]] || poz*2+1 > L)
        {
            swap(H[poz], H[poz*2]);
            swap(POZ[H[poz]], POZ[H[poz*2]]);
            poz = poz * 2;
        }
        else
        {
            swap(H[poz], H[poz*2+1]);
            swap(POZ[H[poz]], POZ[H[poz*2+1]]);
            poz = poz *2 +1;
        }
    }
}

void insert_heap(int x)
{
    H[++L] = x;
    POZ[x] = L;
    upheap(L);
}

int remove_head()
{
    int x = H[1];
    swap(H[1], H[L--]);
    POZ[H[1]] = 1;
    POZ[x] = 0;
    downheap(1);
    return x;
}

int main()
{
    FILE *in = fopen(iname, "r");
    FILE *out = fopen(oname, "w");
    fscanf(in, "%d %d", &N, &M);
    for(int i = 0; i < M; i++)
    {
        int x,y,c;
        fscanf(in, "%d %d %d", &x, &y, &c);
        graf[x].push_back(make_pair(y,c));
        graf[y].push_back(make_pair(x,c));
    }
    for(int i = 1; i <= N; i++)
        COST[i] = INF;
    insert_apm(1);
    for(int i = 2; i <= N; i++)
        insert_heap(i);

    for(int i = 2; i <= N; i++)
    {
        int x = remove_head();
        insert_apm(x);
        apm.push_back(make_pair(x, TATA[x]));
        cost_total += COST[x];
        for(iter it = graf[x].begin(); it != graf[x].end(); ++it)
            if(POZ[it->first]) upheap(POZ[it->first]);
    }
    fprintf(out, "%d\n%d\n", cost_total, N-1);
    for(int i = 0; i < N - 1; i++)
    {
        fprintf(out, "%d %d\n", apm[i].first, apm[i].second);
    }
    return 0;
}