#include <iostream>
#include <fstream>


struct muchie {
    int x;
    int y;
    int valoare;
};
using namespace std;

muchie v[400005];
int n;
int m;
muchie t[400005];
int a[2005][2005];

void citire() {
    cout<<"Dati numarul de varfuri ale grafului ";
    cin>>n;
    cout<<"Dati numarul de muchii ale grafului";
    cin>>m;
    for (int i=1; i<=m; ++i)
    {
        cout<<"Dati extermitatile muchiei "<<i<<"\n";
        cout<<"Dati prima extremitate";
        cin>>v[i].x;
        cout<<"Dati a doua extremitate";
        cin>>v[i].y;
        cout<<"Dati valoarea asociata muchiei"<<i;
        cin>>v[i].valoare;
    }
}

void sortare()
{
    bool ok;
    do
    {
        ok=true;
        for (int i=1; i<m; i++)
            if (v[i].valoare<v[i+1].valoare)
            {
                muchie aux=v[i]; v[i]=v[i+1];v[i+1]=aux;
                ok=false;
            }
    }
    while (!ok);
}


void fa_matrice_adiacenta (int a[2005][2005], muchie v[400005])
{
    for (int i=1; i<=m; i++)
    {
        a[v[i].x][v[i].y]=1;
        a[v[i].y][v[i].x]=1;
    }
}

void elimina_muchie(int k)
{
    for (int i=k; i<=m-1; i++)
        v[i]=v[i+1];
    --m;
}

bool conex()
{
    int c[2005];
    c[1]=1;
    int pi=1;
    int ps=0;
    int viz[2005];
    for (int i=1; i<=n; ++i)
        viz[i]=0;
    viz[1]=1;
    while (ps<pi)
    {
        ++ps;
        for (int i=1; i<=n; i++)
        {
            if (a[c[ps]][i]==1 && viz[i]==0)
            {
                pi++;
                c[pi]=i;
                viz[i]=1;
            }
        }
    }
    return (pi==n);
}

void aplica_algoritm()
{
    int k=1;
    while (k<=m)
    {
        a[v[k].x][v[k].y]=0;
        a[v[k].y][v[k].x]=0;
        if (conex())
        {
            elimina_muchie(k);
        }
        else
        {
            a[v[k].x][v[k].y]=1;
            a[v[k].y][v[k].x]=1;
            ++k;
        }
    }
}

int calculeazaValoare()
{
    int s=0;
    for (int i=1; i<=m; i++)
        s+=v[i].valoare;
    return s;
}


int main() {
    //citire();
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for (int i=1; i<=m; i++)
        f>>v[i].x>>v[i].y>>v[i].valoare;
    sortare();
    fa_matrice_adiacenta(a,v);
    aplica_algoritm();
    int s=calculeazaValoare();
    g<<s<<"\n"<<n-1<<"\n";
    for (int i=1; i<=m; ++i)
        g<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}