#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const char inFile[] = "apm.in";
const char outFile[] = "apm.out";

unsigned N, M;

typedef struct edge_type{
    unsigned x, y;
    short cost;
    struct edge_type* next;
} edge_type;

edge_type* priorityQ = NULL;

void append(unsigned a, unsigned b, short c)
{
    edge_type* new_edge = (edge_type*)malloc(sizeof(edge_type));
    new_edge->x = a;
    new_edge->y = b;
    new_edge->cost = c;
    new_edge->next = NULL;
    if(priorityQ == NULL)
    {
        priorityQ = new_edge;
        return;
    }
    if(new_edge->cost <= priorityQ->cost)
    {
        new_edge->next = priorityQ;
        priorityQ = new_edge;
        return;
    }
    edge_type* pred = priorityQ, *curr = priorityQ->next;
    while(curr != NULL)
    {
        if(new_edge->cost <= curr->cost)
        {
            pred->next = new_edge;
            new_edge->next = curr;
            return;
        }
        pred = curr;
        curr = curr->next;
    }
    pred->next = new_edge;
}

int main(void)
{
    freopen(inFile, "r", stdin);
    cin >> N >> M;
    vector<pair<unsigned, short> > v[N + 1];
    for(unsigned i = 0; i < M; ++i)
    {
        unsigned X, Y;
        short C;
        cin >> X >> Y >> C;
        v[X].pb(make_pair(Y, C));
        v[Y].pb(make_pair(X, C));
    }
    fclose(stdin);
    bool viz[N + 1];
    memset(viz, false, N + 1);
    set<pair<unsigned, unsigned> > s;
    unsigned curr = 1, sel = 1;
    viz[curr] = true;
    long long costMin = 0;
    while(sel != N)
    {
        for(unsigned i = 0; i < v[curr].size(); ++i)
            if(!viz[v[curr][i].first])
                append(curr, v[curr][i].first, v[curr][i].second);
        unsigned node = 0;
        pair<unsigned, unsigned> edge;
        while(!node)
        {
            edge = {priorityQ->x, priorityQ->y};
            if(!viz[edge.first] || !viz[edge.second])
            {
                if(!viz[edge.first])
                    node = edge.first;
                else node = edge.second;
                costMin += priorityQ->cost;
            }
            priorityQ = priorityQ->next;
        }
        s.insert(edge);
        curr = node;
        viz[curr] = true;
        ++sel;
    }
    freopen(outFile, "w", stdout);
    cout << costMin << endl << N - 1;
    for(auto k : s)
        cout << endl << k.first << ' ' << k.second;
    fclose(stdout);
    return 0;
}