#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int VMAX = 200000, INF = 1e8;

struct edge
{
    int v1, v2, w;
};
bool operator <(const edge& x, const edge& y) {
    return x.w > y.w;
}
priority_queue<edge, vector<edge>> pq;

edge apm[VMAX - 1];
vector<edge> lists[VMAX];
bool vis[VMAX];

int main()
{
    int nre, nrv, i, minw, j, elen, newv;
    edge emin, e;
    FILE *fin = fopen("apm.in", "r");

    fscanf(fin, "%d%d", &nrv, &nre);
    emin.w = INF;
    for (i = 0; i < nre; i++)
    {
        fscanf(fin, "%d%d%d", &e.v1, &e.v2, &e.w);
        lists[e.v1].push_back(e);
        lists[e.v2].push_back(e);
        if (emin.w > e.w)
            emin = e;
    }
    fclose(fin);

    elen = lists[emin.v1].size();
    vis[emin.v1] = 1;
    for (i = 0; i < elen; i++)
        pq.push(lists[emin.v1][i]);

    minw = j = 0;
    while (!pq.empty())
    {
        emin = pq.top();
        pq.pop();
        newv = emin.v1;
        if (vis[newv] == 1)
            newv = emin.v2;
        if (vis[newv] == 0)
        {
            vis[newv] = 1;
            minw += emin.w;
            apm[j++] = emin;
            elen = lists[newv].size();
            for (i = 0; i < elen; i++)
                pq.push(lists[newv][i]);
        }
    }

    FILE *fout = fopen("apm.out", "w");
    nrv--;
    fprintf(fout, "%d\n%d\n", minw, nrv);
    for (i = 0; i < nrv; i++)
        fprintf(fout, "%d %d\n", apm[i].v1, apm[i].v2);
    fclose(fout);
    return 0;
}