#include <fstream>
#include<algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");
struct muc {int x,y,cost;};
muc mu[400005];
int c[200005];
int v[200005];
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,c2;
    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--;
            c2=c[mu[i].y];
            co+=mu[i].cost;
            v[cn]=i;
            for(int j=1; j<=n;j++)
                if(c[j]==c2)
                    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);
}