#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin  ("apm.in");
ofstream fout ("apm.out");

const int INFINIT = 1005;
const int NMAX = 200005;

vector < vector < pair < int, int > > > costuri(NMAX);
vector < int > vx;
vector < int > vy;
int tati[NMAX], N, M;
int dist[NMAX];
int poz_in_heap[NMAX];
bool vizitat[NMAX];
long long cost_minim;
int nod_start = -1;

struct comp {
    bool operator()(int x, int y) {
        return dist[x] > dist[y];
    }
};

priority_queue < int, vector < int >, comp> heap;

void init()
{
    for(int i = 0; i < NMAX; i++)
        dist[i] = INFINIT;
}

void citire()
{
    fin >> N >> M;
    int x, y, cost;
    int cost_min = 1005;
    for(int i = 0; i < M; i++)
    {
        fin >> x >> y >> cost;
        pair < int, int > pair_1 = make_pair(y, cost);
        pair < int, int > pair_2 = make_pair(x, cost);
        costuri[x].push_back(pair_1);
        costuri[y].push_back(pair_2);
        if(cost < cost_min)
        {
            cost_min = cost;
            nod_start = x;
        }
    }
    init();
}

void Prim()
{
    for(unsigned int i = 0; i < costuri[nod_start].size(); i++)
    {
        tati[costuri[nod_start][i].first] = nod_start;
        dist[costuri[nod_start][i].first] = costuri[nod_start][i].second;
        heap.push(costuri[nod_start][i].first);
    }
    vizitat[nod_start] = 1;

    while(!heap.empty())
    {
        int mini = heap.top();
        heap.pop();

        if(vizitat[mini])
            continue;
        cost_minim += dist[mini];
        vizitat[mini] = 1;
        vx.push_back(tati[mini]); vy.push_back(mini);
        for(unsigned int k = 0; k < costuri[mini].size(); k++)
            if(costuri[mini][k].second < dist[costuri[mini][k].first])
            {
                tati[costuri[mini][k].first] = mini;
                dist[costuri[mini][k].first] = costuri[mini][k].second;
                heap.push(costuri[mini][k].first);
            }
    }
}

void afisare()
{
    fout << cost_minim << '\n';
    fout << N - 1 << '\n';
    for(int i = 0; i < N - 1; i++)
        fout << vx[i] << ' ' << vy[i] << '\n';
}

int main()
{
    citire();
    Prim();
    afisare();
    return 0;
}