#include <bits/stdc++.h>
#define Nmax 180

using namespace std;

ifstream f("ferma32.in");
ofstream g("ferma32.out");

struct muchie
{
    int x,y,cost;
}graf[Nmax];

vector<int>tata(Nmax);
vector<int>rang(Nmax);
pair<int,int> p[Nmax];

int n,m,k,total;


bool Compare(muchie a, muchie b)
{
    return a.cost < b.cost;
}
void Read()
{
    f>>n>>m;
    tata.resize(n);
    rang.resize(n);
    for(int i=1;i<=m;i++)
        f>>graf[i].x>>graf[i].y>>graf[i].cost;

    sort(graf+1 , graf+m+1, Compare);

    for(int i=1;i<=n;i++)
    {
        tata[i] = i;
        rang[i] = 1;
    }
    f.close();
}

int Find(int nod)
{
    if(nod == tata[nod])
        return nod;
    Find(tata[nod]);
}

void Uneste(int x,int y)
{
    if(rang[x] < rang[y])
        tata[x] = y;
    if(rang[x] > rang[y])
        tata[y] = x;
    if(rang[x] == rang[y])
    {
        tata[x] = y;
        rang[y]++;
    }
}

void Afisare()
{
    g<<total<<"\n";
    g<<k<<"\n";

    for(int i=1;i<=k;i++)
        g<<p[i].first<<" "<<p[i].second<<"\n";
    g.close();
}

void Solve()
{
    for(int i=1;i<=m;i++)
    {
        int tata_x = Find(graf[i].x);
        int tata_y = Find(graf[i].y);

        if(tata_x != tata_y)
        {
            Uneste(tata_x, tata_y);
            p[++k].first = graf[i].y;
            p[k].second = graf[i].x;
            total += graf[i].cost;
        }
    }
    Afisare();
}
int main()
{
    Read();
    Solve();
    return 0;
}