#include <cstdio>
#include <vector>
using namespace std;
int n,m,i,c,s,x,y,v[200001];
struct muchie
{
    int x,y,cost;
}mc,a[400001];
vector <muchie> vecin[200001];
vector <muchie>::iterator it;
vector <muchie> arb;
void pushup(int x)
{
    int val;
    val=a[x].cost;
    while(x>1 && val<a[x/2].cost)
    {
        swap(a[x],a[x/2]);
        x/=2;
    }
}
void pushdown(int x)
{
    int son;
    do
    {
        son=0;
        if(x*2<=m)
        {
            son=x*2;
            if(son+1<=m && a[son+1].cost<a[son].cost)
                son++;
            if(a[son].cost>=a[x].cost)
                son=0;
        }
        if(son)
        {
            swap(a[x],a[son]);
            x=son;
        }
    }
    while(son);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    while(m)
    {
        scanf("%d %d %d\n",&x,&y,&c);
        mc.x=x;
        mc.y=y;
        mc.cost=c;
        vecin[x].push_back(mc);/// vecinii nodului x
        mc.x=y;
        mc.y=x;
        vecin[y].push_back(mc);/// vecinii nodului y
        m--;
    }
    v[1]=1;/// vizitez nodul 1
    for(it=vecin[1].begin();it!=vecin[1].end();it++)
    {
        mc=*it;
        a[++m]=mc;/// introduc vecinii nodului 1 in heap
        pushup(m);
    }
    for(i=1;i<n;i++)
    {
        mc=a[1];
        s+=mc.cost;
        a[1]=a[m];
        m--;
        pushdown(1);/// elimin muchia de cost minim din heap,ce are legatura cu arborele
        arb.push_back(mc);/// introduc muchia in arbore
        v[mc.y]=1;/// vizitez cealalta extremitate a muchiei
        for(it=vecin[mc.y].begin();it!=vecin[mc.y].end();it++)
            if(!v[(*it).y])
            {
                a[++m]=*it;
                pushup(m);/// introduc in heap muchiile ce contin noduri nevizitate
            }
        while(v[a[1].x]==1 && v[a[1].y]==1)/// cat timp ambele noduri ale primei muchii sunt vizitate
        {
            a[1]=a[m];
            m--;
            pushdown(1);/// sterg muchia
        }
    }
    printf("%d\n%d\n",s,n-1);
    for(it=arb.begin();it!=arb.end();it++)
    {
        mc=*it;
        printf("%d %d\n",mc.x,mc.y);
    }
    return 0;
}