#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define nmax 100010
using namespace std;
FILE *f,*g;
struct cp{int y,c; } ax;
struct cp2{int x,y;} ax2;
struct cp3{int x,y,c;} ax3;
vector <cp> a[nmax];
vector <cp2> sol;
bool bif[nmax];
int n,m,cos=0;

class comp {
public:

bool operator() (const cp3& lhs,const cp3& rhs) const {
    return ( lhs.c>rhs.c );
    }
};
typedef priority_queue<cp3,vector<cp3>, comp >  heap;
heap H;


void read() {
int i,x,y;
cp ax;
fscanf(f,"%d%d",&n,&m);

for (i=1;i<=m;i++) {
    fscanf(f,"%d%d%d",&x,&y,&ax.c);
    ax.y=y;
    a[x].push_back(ax);
    ax.y=x;
    a[y].push_back(ax);
    }

}
void solve( ) {
int i,x=1,j;

bif[x]=true;


for (i=1;i<=n-1;i++) {
    for (j=0;j<a[x].size();j++)
        if (!bif[a[x][j].y]) {
            ax3.x=x;
            ax3.y=a[x][j].y;
            ax3.c=a[x][j].c;
            H.push(ax3);
            }
    while (bif[H.top().y]==true) H.pop();
    x=H.top().y;
    bif[x]=true;
    ax2.x=H.top().x;
    ax2.y=H.top().y;
    cos=cos+H.top().c;
    H.pop();
    sol.push_back(ax2);
    }

fprintf(g,"%d\n",cos);
fprintf(g,"%d\n",sol.size());

for (vector <cp2>::iterator q=sol.begin();q!=sol.end();q++)
	fprintf(g,"%d %d\n",*q);



}




int main() {
f=fopen("apm.in","r");
g=fopen("apm.out","w");

read();
solve();



fclose(g);
return 0;
}