#include <fstream>
#include <algorithm>

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

struct el
{
    int x,y,c;
}a[400003];

int n,m,t[200003],sol[200003],sum,k;


bool cmp(el a,el b)
{
    return a.c<b.c;
}

int getTata(int val)
{
    while(t[val]!=val)
        val=t[val];
    return val;
}


int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a[i].x>>a[i].y>>a[i].c;
        t[i]=i;
    }
    sort(a+1,a+m+1,cmp);
    int muchii=n-1;
    for(int i=1;i<=m&&muchii>0;i++)
    {
        int t1=getTata(a[i].x),t2=getTata(a[i].y);
        if(t1!=t2)
        {
            muchii--;
            sum+=a[i].c;
            t[t1]=t2;
            sol[++k]=i;
        }
    }
    fout<<sum<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++)
        fout<<a[sol[i]].x<<" "<<a[sol[i]].y<<"\n";
    return 0;
}