#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct{int in,out,cost;}a[400001],aux;
int n,m,x,L[200001];
void sortare(){for(int i=1;i<m;i++)for (int j=i+1;j<=m;j++) if (a[i].cost>a[j].cost) aux=a[i],a[i]=a[j],a[j]=aux; }
void load()
{
    f>>n>>m;
    for (int i=0;i<=m;i++) f>>a[i].in>>a[i].out>>a[i].cost;
    for (int i=1;i<=n;i++) L[i]=i;
    sortare();
}
void apm()
{int s=0,nr=0,k=0;bool ok[801][801];
    for (int i=0;i<=m;i++)
        if (L[a[i].in]!=L[a[i].out])
        {
            s+=a[i].cost,nr++,ok[a[i].in][a[i].out]=true;x=L[a[i].out];L[a[i].out]=L[a[i].in];
            for (int j=1;j<=n;j++) if ( L[j]==x) L[j]=L[a[i].in];
        }
    g<<s<<'\n'<<nr<<'\n';
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
        if (ok[i][j]) g<<j<<' '<<i<<'\n';

}
int main()
{
    load(),apm();
    return 0;
}