#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct nod
{
    int x, y, cost;
};

nod lista[32390];
int t[260], c[260], sol[64800], n, m, k, costtotal;

inline int Find(int x)     /// imi gaseste radacina
{
    int y,z;
    y=x;
    while (t[x]!=0)
        x=t[x];
    while (y!=x)
    {
        z = t[y];
        t[y] = x;
        y = z;
    }

    return x;
}

inline void Union(int x, int y)   /// imi uneste arbori
{
    if (c[x] >= c[y])
    {
        c[x]+=c[y];
        c[y]=0; // nu neaparat
        t[y]=x;
    }
    else
    {
        c[y]+=c[x];
        c[x]=0; // nu neaparat
        t[x]=y;
    }
}

inline bool compara (const nod nr1, const nod nr2) /// compara costurile boss
{
    return (nr1.cost < nr2.cost);
}

inline void Citire()  /// citire si calcul costtotal
{
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        fin>>lista[i].x;
        fin>>lista[i].y;
        fin>>lista[i].cost;
    }
}

inline void Rezolva()
{
    int i,j,x,y,kanye;
    sort(lista + 1, lista+m+1, compara);
    
    int suma=0;
    for (i=1; i<=n; i++)
    {
        t[i] = 0;
        c[i] = 1;
    }
    kanye=0;
    for (i = 1; i <= m; i++)
    {
        x = Find(lista[i].x);
        y = Find(lista[i].y);
        if (x != y)
        {
            Union(x, y);
            suma+= lista[i].cost;
            lista[i].cost = -100000;
            kanye++;
        }
    }
    fout << suma <<"\n";
    fout << kanye <<"\n";
    for (i=1; i<=m; i++)
    {
        if (lista[i].cost == -100000)
        {
            fout << lista[i].x << " " << lista[i].y << "\n";
        }
    }
}

int main ()
{
    Citire();
    Rezolva();
    fin.close();
    fout.close();
    return 0;
}