#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
using namespace std;

const int Nmax = 200001;

#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f

int dist[Nmax];
int viz[Nmax], p[Nmax];

int n, m;
vector<pair<int, int> > vecin[Nmax];

set<pair<int,int> > Q;
int cost_arbore;

void citire()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        vecin[x].push_back(make_pair(y, c));
        vecin[y].push_back(make_pair(x, c));
    }
}

void prim()
{
    memset(dist, 0x3f, sizeof(dist));
    Q.insert(make_pair(0, 1));
    dist[1] = 0;
    int nr_m_select = n;

    while (Q.size() && nr_m_select)
    {
        int nod = (*Q.begin()).second;
        Q.erase(Q.begin());

        --nr_m_select;
        cost_arbore += dist[nod];
        viz[nod] = 1;

        for (int i = 0; i < vecin[nod].size(); ++i)
        {
            int nod_vecin = vecin[nod][i].first;
            int cost = vecin[nod][i].second;

            if (dist[nod_vecin] > cost)
            {
                dist[nod_vecin] = cost;
                p[nod_vecin] = nod;

                Q.insert(make_pair(dist[nod_vecin], nod_vecin));
            }
        }
    }
}

void afisare()
{
    printf("%d\n", cost_arbore);
    printf("%d\n", n - 1);
    for (int i = 2; i <= n; ++i)
        printf("%d %d\n", p[i], i);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    citire();
    prim();
    afisare();

    return 0;
}