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

using namespace std;

struct muchie
{
    int x,y,c;
};

struct cmp
{
    bool operator()(const muchie& a, const muchie& b) const
    {
        return a.c > b.c;
    }
};

ifstream f("apm.in");
ofstream g("apm.out");

int main()
{
    priority_queue<muchie,vector<muchie>,cmp>  heap;
    int n,m,cost = 0,aux = 0;
    muchie k;
    f>>n>>m;
    int *arbore = new int[n+1];     // daca un nod a fost adaugat sau nu in arborele partial
    muchie *muc = new muchie[m];
    vector<muchie> v[n+1];  //muchiile adiacente la un nod i
    vector<muchie> arbore_m;  // muchiile din arborele partial
    for(int i=1;i<n+1;++i)
    {
        arbore[i] = 0;
    }
    for(int i=0;i<m;++i)
    {
        f>>muc[i].x>>muc[i].y>>muc[i].c;
        v[muc[i].x].push_back(muc[i]);
        v[muc[i].y].push_back(muc[i]);
    }


    for(unsigned int i = 0;i<v[1].size();++i)
    {
        heap.push(v[1][i]);
    }
    arbore[1] = 1;
    ++aux;
    while(aux <= n-1)
    {
        k = heap.top();
        heap.pop();
        if(arbore[k.x] == 0)
        {
            arbore[k.x] = 1;
            ++aux;
            cost += k.c;
            arbore_m.push_back(k);
            for(unsigned int i = 0;i<v[k.x].size();++i)
            {
                heap.push(v[k.x][i]);
            }
        }
        if(arbore[k.y] == 0)
        {
            arbore[k.y] = 1;
            ++aux;
            cost += k.c;
            arbore_m.push_back(k);
            for(unsigned int i = 0;i<v[k.y].size();++i)
            {
                heap.push(v[k.y][i]);
            }
        }
    }
    g<<cost<<"\n"<<n-1<<"\n";
    for(unsigned int i = 0;i<arbore_m.size();++i)
    {
        g<<arbore_m[i].x<<" "<<arbore_m[i].y<<"\n";
    }
    return 0;
}