#include <fstream>
#include<algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");
struct muc {int x,y,cost;};
muc mu[100000];
int c[100000];
int v[100000];
void citire();
void rez();
bool comp (muc a,muc b);
int n,m;
int main()
{
    citire();
    rez();
    return 0;
}

void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>mu[i].x>>mu[i].y>>mu[i].cost;

}

void rez ()
{
    int i,cn;
    int co=0;
    sort(mu+1, mu+1+m, comp);
    for(i=1;i<=n;i++) c[i]=i;
    cn=n-1;
    i=0;
    while (cn)
    {
        ++i;
        if(c[mu[i].x] != c[mu[i].y])
        {
            cn--;
            co+=mu[i].cost;
            v[cn]=i;
            for(int j=1; j<=n;j++)
                if(c[j]==c[mu[i].y])
                    c[j]=c[mu[i].x];
        }
    }
    fout<<co<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
    {
        fout<<mu[v[i]].x<<" "<<mu[v[i]].y<<'\n';
    }
}

bool comp (muc a, muc b)
{
    return (a.cost < b.cost);
}