#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAX 200020

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;

struct muchie
{
    int x,y,cost;
};
vector<muchie> e;
vector<muchie> apm;
int viz[MAX],cost;

int comp(muchie a,muchie b)
{
    return a.cost < b.cost;
}

int citeste()
{
    int i;
    f>>n>>m;
    e.resize(m);
    for (i=0;i<m;++i)
        f>>e[i].x>>e[i].y>>e[i].cost;
    sort(e.begin(),e.end(),comp);
}

int solutie()
{
    int i,k;
    cost=0;
    apm.push_back(e[0]);
    viz[e[0].x]=viz[e[0].y]=1;
    cost=cost+apm[0].cost;
    for(k=0;k<n-2;++k)
    {
        i=1;
        while (viz[e[i].x]==viz[e[i].y]) ++i;
        apm.push_back(e[i]);
        viz[e[i].x]=viz[e[i].y] = 1;
        cost=cost+e[i].cost;
    }
}

int scrie()
{
    int i;
    g<<cost << "\n";
    g<<apm.size()<<endl;
    for (i=0;i<apm.size();++i)
        g<<apm[i].x<<" "<<apm[i].y<<"\n";
}

int main()
{
    citeste();
    solutie();
    scrie();

    f.close();
    g.close();

    return 0;
}