#include <fstream>
#include <algorithm>
using namespace std;
struct muchie{int x,y,c;};
int m,n,t[200001],h[200001],sol[200001],cost,i,k;
muchie a[400001];
void citeste()
{
    ifstream f("apm.in");
    f>>n>>m;
    for(int i=1;i<=m;i++) f>>a[i].x>>a[i].y>>a[i].c;
    f.close();
}
bool comp(muchie a, muchie b)
{
    return a.c<b.c;
}
bool verifica(int x, int y)
{
    int r1,r2,x1,x2,c;
    r1=x;r2=y;
    while(r1!=t[r1])r1=t[r1];
    while(r2!=t[r2])r2=t[r2];

    if(r1==r2) return false;

    while(t[x]!=r1)x1=t[x],t[x]=r1,x=x1;
    while(t[y]!=r2)x2=t[y],t[y]=r2,y=x2;

    if(h[r1]>h[r2])t[r2]=r1,c=r1;
    else t[r1]=r2,c=r2;

    if(h[r1]==h[r2])h[c]++;

    return true;
}
int main()
{
    citeste();
    for(i=1;i<=n;i++) t[i]=i,h[i]=1;
    sort(a+1,a+m+1,comp);
    i=1;
    while(k<n-1)
    {
        if(verifica(a[i].x,a[i].y)) cost+=a[i].c,sol[++k]=i;
        i++;
    }
    ofstream g("apm.out");
    g<<cost<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        g<<a[sol[i]].x<<" "<<a[sol[i]].y<<'\n';
    g.close();
    return 0;
}