#include <fstream>
#include <algorithm>

using namespace std;
int t[200005],h[200005];
int f(int x)
    {
    while (t[x]!=0)
        x=t[x];
    return x;
    }
struct muchie
    {int x,y,c;}e[400002],al[200005];
bool comp(muchie a,muchie b)
    {
    return a.c<b.c;
    }
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    long long int s=0;
    int nralese=0;
    int n,m,x1,x2,r1,r2;
    fin>>n>>m;
    for (int i=1;i<=m;i++)
        fin>>e[i].x>>e[i].y>>e[i].c;
    sort(e+1,e+m+1,comp);
    for (int i=1;i<=m&&nralese<n-1;i++)
        {
        x1=e[i].x;
        x2=e[i].y;
        r1=f(x1);
        r2=f(x2);
        if (r1!=r2)
            {
            nralese++;
            al[nralese]=e[i];
            s+=e[i].c;
            if (h[r1]<h[r2])
                t[r1]=r2;
            else if (h[r1]>h[r2])
                t[r2]=r1;
            else
                {
                t[r1]=r2;
                h[r1]++;
                }
            }
        }
    fout<<s<<"\n";
    fout<<nralese<<"\n";
    for (int i=1;i<=nralese;i++)
        fout<<al[i].y<<" "<<al[i].x<<"\n";
    return 0;
}