#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
 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[A[nrmsel]].cost;
        }

        if(c[g[i].n1]<c[g[i].n2]){
            maxi=c[g[i].n2];
            mini=c[g[i].n1];
        }
        else{
            maxi=c[g[i].n1];
            mini=c[g[i].n2];
        }
        for(j=1;j<=n;j++)
            if(c[j]==maxi)
                c[j]=mini;
    }
    afisare();

return 0;
}