#include<cstdio>
#include<algorithm>
using namespace std;
struct graf{int n1,n2,cost;};
graf g[400101];
int c[400101],A[400101];
bool cmp(graf a, graf b){
    return (a.cost<b.cost);
}
int n,m;
void citire(){
    int i;

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&g[i].n1,&g[i].n2,&g[i].cost);
    for(i=1;i<=n;i++)
        c[i]=i;
}
int suma=0;
void afisare(){

    printf("%d\n%d\n",suma,n-1);
    for(int i=1;i<=n-1;i++)
            printf("%d %d\n",g[A[i]].n1,g[A[i]].n2);



}
int root(int node)
{
    if (c[node] == node) {
        return node;
    } else {
        c[node] = root(c[node]);
        return c[node];
    }
}

void unify(int node1, int node2)
{
    c[root(node1)] = root(node2);
}
 main(){
     freopen("apm.in","r",stdin);
     freopen("apm.out","w",stdout);

    int nrmsel,i,maxi,mini,j;
    citire();

    sort(g+1,g+m+1,cmp);
    nrmsel=0;

    for(i=1;nrmsel<n-1;i++)
        if(c[g[i].n1]!=c[g[i].n2]){
            A[++nrmsel]=i;
            suma+=g[i].cost;
            unify(g[i].n1, g[i].n2);
        }

    afisare();

return 0;
}