#include <fstream>
#include <algorithm>
using namespace std;

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

struct muchie{int x,y,cost;}c[400001];
int t[200001],adanc[200001],n,m,z,cost,v[200001];

bool cmp(muchie a, muchie b){return a.cost<b.cost;}
int radacina_arborelui(int a)
{
    while(t[a])a=t[a];
    return a;
}

void unire(int a, int b)
{
    if(adanc[a]==adanc[b]){t[b]=a; adanc[a]++;}
    else if(adanc[a]<adanc[b])t[a]=b;
    else t[b]=a;
}

int main()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>c[i].x>>c[i].y>>c[i].cost;
    sort(c+1,c+m+1,cmp);

    int k=1,nr=0;
    while (k<=m and nr<n)
    {
        int x=radacina_arborelui(c[k].x);
        int y=radacina_arborelui(c[k].y);
        if(x!=y)
        {
            unire(x,y);
            z++;
            v[z]=k;
            cost+=c[k].cost;
            nr++;
        }
        k++;
    }

    fout<<cost<<endl<<z<<endl;
    for(i=1; i<=z; i++) fout<<c[v[i]].x<<" "<<c[v[i]].y<<endl;
    return 0;
}