#include <bits/stdc++.h>
#define NMAX 200005
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");

struct muchie
{
    int x, y, c;
    bool operator() (const muchie & a, const muchie & b)
    {
        return a.c > b.c;
    }
} aux, naux ;
priority_queue<muchie, vector <muchie>, muchie > pr;
int n, m, costTotal = 0;
vector <muchie> a[NMAX];
bitset<NMAX> b;

void AdaugNod(int nod)
{
    b[nod] = 1;
    for (int i = 0; i < a[nod].size(); i++)
    {
        aux = a[nod][i];
        int nextNod = aux.x;
        if (nextNod == nod)
            nextNod = aux.y;
        if (b[aux.x] * b[aux.y] == 1)
            continue;
        pr.push(aux);
    }
}
muchie Delete()
{
    if (pr.empty())
        return naux;
    aux = pr.top();
    pr.pop();
    while (!pr.empty() && b[aux.x] * b[aux.y])
    {
        aux = pr.top();
        pr.pop();
    }
    if (b[aux.x] * b[aux.y] == 1)
        return naux;
    return aux;
}

void Solve()
{
    AdaugNod(1);
    muchie d;
    do
    {
        d = Delete();
        int q = d.x;
        if (b[q] == 1)
            q = d.y;
        AdaugNod(q);
        a[0].push_back(d);
        costTotal += d.c;
    }
    while (d.x != 0);
}

int main()
{
    f>>n>>m;
    for (int x, y, c, i = 0; i < m; i++)
    {
        f>>x>>y>>c;
        aux.x = x;
        aux.y = y;
        aux.c = c;
        a[x].push_back(aux);
        a[y].push_back(aux);
    }
    Solve();
    g<<costTotal<<'\n'<<n - 1<<'\n';
    for (int i = 0; i < a[0].size() - 1; i++)
        g<<a[0][i].x<<' '<<a[0][i].y<<'\n';
    return 0;
}