///alg prim
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct elem{int x,y;
float c;};
elem u[400001];
int viz[200001],i,j,n,m=1,k,s[400001],f;
float cost;


void citire(){in>>n>>m;
for(i=1;i<=m;i++)in>>u[i].x>>u[i].y>>u[i].c;
in.close();
}



void rez(){
    cost+=u[1].c;
viz[u[1].x]=viz[u[1].y]=1;
k=1;s[k]=1;
    while(k<=n-2){
        for(i=2;i<=m;i++)
        if(viz[u[i].x]+viz[u[i].y]==1){s[++k]=i;
                           cost+=u[i].c;
viz[u[i].x]=viz[u[i].y]=1;
break;}}
}

bool cmp(elem a,elem b){
return a.c<b.c;
}

int main(){
citire();
sort(u+1,u+m+1,cmp);///pas1
rez();
out<<cost<<"\n";
out<<n-1<<"\n";
for(i=1;i<=k;i++)
     out<<u[s[i]].x<<" "<<u[s[i]].y<<"\n";
return 0;}