#include <algorithm>
#include <fstream>

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

struct muchie{
    int x,y,cost;
}e[400002],apm[200002];
int tata[200002],nr[200002];

bool cmp(muchie x,muchie y)
{
    return x.cost<y.cost;
}
int myfind(int x)
{
    while(tata[x]!=0) x=tata[x];
    return x;
}

void myunion(int a, int b)
{

        if(nr[a]<nr[b])tata[a]=b;
        else if(nr[a]>nr[b])tata[b]=a;
            else if(nr[a]==nr[b])
            {
                tata[a]=b;
                nr[b]++;
            }

}


int main()
{
    int n,m,i,s=0,a,b,x,y;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>e[i].x>>e[i].y>>e[i].cost;
    sort(e+1,e+m+1,cmp);
    int cnt=0;
    for(i=1;i<=m;i++)
    {
        a=e[i].x;
        b=e[i].y;
        x=myfind(a);
        y=myfind(b);
        if(x!=y)
        {
            cnt++;
            apm[cnt]=e[i];
            s=s+e[i].cost;
            myunion(x,y);
            if(cnt==n-1)
                break;
        }
    }
    fout<<s<<endl;
    fout<<cnt<<endl;
    for(i=1;i<=cnt;i++)
        fout<<apm[i].x<<" "<<apm[i].y<<endl;
    return 0;
}