#include <fstream>
#include <algorithm>
#define NMAX 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,tata[NMAX],s,nr;
struct du{
    int x,y,cost;}muchii[2*NMAX];
struct du2{
    int x,y;}sol[2*NMAX];
int cmp(du a, du b){
    return a.cost<b.cost;}
int root(int nod){
    while(tata[nod])
        nod=tata[nod];
    return nod;
    }

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
    sort(muchii+1,muchii+m+1,cmp);
    for(i=1;i<=m;i++)
        if(root(muchii[i].x)!=root(muchii[i].y)){
            tata[root(muchii[i].x)]=root(muchii[i].y);

                s+=muchii[i].cost;
                sol[++nr].x=muchii[i].x;
                sol[nr].y=muchii[i].y;
            }

        g<<s<<'\n'<<n-1<<'\n';
        for(i=1;i<=n-1;i++)
            g<<sol[i].x<<" "<<sol[i].y<<'\n';
    return 0;
}