#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[400120];
int t[200009], c[200009],  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 cmp (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, suma, cnt;
    
    sort(lista+1, lista+m+1, cmp);
    suma = cnt = 0;
    for (i=1; i<=m; i++)
    {
       x = Find(lista[i].x); y = Find(lista[i].y);    
       if (x != y)
        {
             Union(x, y);
             cnt++;
             suma += lista[i].cost;
             lista[i].cost = -100000;
        }
    }
    fout << suma << "\n" << cnt << "\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;
}