#include <bits/stdc++.h>
using namespace std;
#define N 400001
#define f first
#define s second
ifstream in("apm.in");
ofstream out("apm.out");
struct graf{
    int c;
    int x;
    int y;
} G[N];
bool V[N];
pair<int,int> r[N];
bool comp(graf& i, graf& j){
    return (i.c<j.c);
}
int main(){
    int n,m,i,a,b,d,j;
    in>>n>>m;
    for(i=1; i<=m; ++i){
		in>>a>>b>>d;
        G[i].c=d;
        G[i].x=a;
        G[i].y=b;
    }
    sort(G+1, G+m+1, comp);
    for(i=1; i<=n; ++i)
        V[i]=0;
    i=1;
    V[G[1].x]=V[G[1].y]=1;
    int ct=G[1].c;
    r[1]=make_pair(G[1].x, G[1].y);
    int k;
    for(k=2; k<=n-1; ++k){
        i=1;
        while(V[G[i].x]==V[G[i].y]) ++i;
        r[k]=make_pair(G[i].x, G[i].y);
        ct+=G[i].c;
        if(V[G[i].x]) V[G[i].y]=1;
        else V[G[i].x]=1;
    }
	out<<ct<<"\n"<<k-1<<"\n";
    for(i=1; i<k; ++i)
        out<<r[i].f<<" "<<r[i].s<<"\n";
    return 0;
}