#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchii
{
    int a,b,c,bag;
} v[400005];
int rep[200005];
bool cmp(muchii a,muchii b)
{
    if(a.c<b.c)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    int n,m,a,b;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>v[i].a>>v[i].b>>v[i].c;
    }

    sort(v+1,v+m+1,cmp);
    int nrmuchii=0,cost=0,ra,rb;
    for(int i=1; i<=n; i++)
    {
        rep[i]=i;
    }
    for(int i=1; i<=m and nrmuchii!=n-1; i++)
    {
        a=v[i].a;
        b=v[i].b;
        ra=rep[a];
        rb=rep[b];
        if(rep[a]!=rep[b])
        {
            v[i].bag=1;
            cost=cost+v[i].c;
            nrmuchii++;
            if(ra>rb)
            {
                for(int i=1; i<=n; i++)
                {
                    if(rep[i]==ra)
                    {
                        rep[i]=rb;
                    }
                }
            }
            else
            {
                for(int i=1; i<=n; i++)
                {
                    if(rep[i]==rb)
                    {
                        rep[i]=ra;
                    }
                }
            }

        }
        //fout<<v[i].a<<" "<<v[i].b<<" "<<" "<<v[i].c<<'\n';
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(int i=1; i<=m; i++)
    {

        if(v[i].bag==1)
        {
            fout<<v[i].a<<" "<<v[i].b<<'\n';
        }
    }
    return 0;
}