//Algoritmul lui Kruskal-Arbore partial de cost minim
#include <cstdio>
#include <algorithm>
#include<fstream>

using namespace std;

int i,aux,n,k,j,p,s,unu,t,m,doi,x,mini,maxi,sol,cont,viz[100010],y,cost;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct coada
{
    int x,y,cost;
}c[200010];
coada a[100010];

bool cmp(coada i,coada j)
{
    return i.cost<j.cost;
}
int parinte(int nod)
{
    int p;
    p=nod;
    while(p!=viz[p])
    {
        p=viz[p];
    }
    return p;

}

void unite(int i,int j)
{
    viz[parinte(i)]=parinte(j);
}

int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        //scanf("%d %d %d",&x,&y,&cost);
        fin>>x>>y>>cost;
        c[i].x=x;
        c[i].y=y;
        c[i].cost=cost;
    }

    sort(c+1,c+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        viz[i]=i;
    }

    cont=0;
    k=0;
    for(i=1;i<=m;i++)
    {
        if(parinte(c[i].x) != parinte(c[i].y))
        {
            a[++cont]=c[i];
            s=s+c[i].cost;

           unite(c[i].x,c[i].y);


        }

    }
    //printf("%d\n%d\n",s,n-1);
    fout<<s<<"\n"<<n-1<<"\n";
    for(i=1;i<=n-1;i++)
    {
        //printf("%d %d\n",a[i].x,a[i].y);
        fout<<a[i].x <<" "<<a[i].y <<"\n";
    }

}