#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie{int x,y,c;};
vector<muchie>m;
vector<int> ar,a;
int n,m1,ct;

bool cmp(const muchie &a, const muchie &b){
    return a.c<b.c;
}

void citire(){
    muchie q;
    scanf("%d %d",&n,&m1);
    for(int i=1;i<=n;i++)
        ar.push_back(i);
    for(int i=1;i<=m1;i++){
        scanf("%d%d%d",&q.x,&q.y,&q.c);
        m.push_back(q);
    }
    a.resize(n,0);
}

void kruskal(){
    int mini,maxi;
    sort(m.begin(),m.end(),cmp);
    int ales=1;
    ar[m[0].x]=1;
    ar[m[0].y]=1;
    a[1]=0;
    ct+=m[0].c;
    for(int i=1;ales<n-1;i++)
        if(ar[m[i].x]!=ar[m[i].y]){
            a[++ales]=i;
            ct+=m[i].c;
            if(ar[m[i].x]<ar[m[i].y])
                mini=ar[m[i].x],maxi=ar[m[i].y];
            else
                mini=ar[m[i].y],maxi=ar[m[i].x];

            for(int j=1;j<=n;j++)if(ar[j]==maxi)ar[j]=mini;
            }


}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    kruskal();
    printf("%d\n%d\n",ct,n-1);
    for(int i=1;i<n;i++)printf("%d %d\n",m[a[i]].x,m[a[i]].y);
    return 0;
}