#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y;
    int c;
};
int cnd(muchie a, muchie b)
{
    if (a.c > b.c) return 0;
    else return 1;
}

int n,m,l[200000],c1[200000],c2[200000];
muchie v[400000];

int main()
{
    int i,j,nr,a,b,ct=0;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cnd);
    for (i=1;i<=n;i++)
        l[i]=i;
    i=1; nr=0;
    while (nr < n-1)
    {
        if (l[v[i].x]!=l[v[i].y])
            {
                nr++;
                a=l[v[i].x];
                b=l[v[i].y];
                for (j=1;j<=n;j++)
                    if (l[j]==b)
                        l[j]=a;
                ct=ct+v[i].c;
                c1[nr]=b;
                c2[nr]=a;
            }
        i++;
    }
    fout<<ct<<'\n'<<nr<<'\n';
    for (i=1;i<=nr;i++)
        {
            fout<<c1[i]<<' '<<c2[i];
            fout<<'\n';
        }
    fin.close();
    fout.close();
    return 0;
}