#include <fstream>
#include <set>

using namespace std;

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

class Edge { public : int mynod, nod, cost, urm; };
int n, m, nr, cost_apm;
int Head[200010], Sol[200010];
Edge M[800010];
multiset < pair < int, int > > Heap;
bool viz[200010];

void Add_Edge(int x, int y, int c)
{
    nr ++;
    M[nr].mynod = x;
    M[nr].nod = y;
    M[nr].cost = c;
    M[nr].urm = Head[x];
    Head[x] = nr;
}

void Add_In_Heap(int nod)
{
    viz[nod] = true;
    for (int p = Head[nod]; p; p = M[p].urm) {
        if (!viz[M[p].nod]) Heap.insert( { M[p].cost, p } );
    }
}

int main()
{
    fin >> n >> m;
    for (int x, y, c, i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        Add_Edge(x, y, c);
        Add_Edge(y, x, c);
    }

    int nod = 1;
    Add_In_Heap(nod);

    for (int i = 1; i < n; i++)
    {
        nod = M[Heap.begin()->second].nod;
        Sol[i] = Heap.begin()->second;
        cost_apm += Heap.begin()->first;
        Heap.erase(Heap.begin());
        while (viz[M[Heap.begin()->second].nod] && viz[M[Heap.begin()->second].mynod]) Heap.erase(Heap.begin());
        Add_In_Heap(nod);
    }

    fout << cost_apm << '\n' << n - 1 << '\n';
    for (int i = 1; i < n; i++) fout << M[Sol[i]].mynod << ' ' << M[Sol[i]].nod << '\n';

    return 0;
}