#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");

struct muchie{
    int x;
    int y;
    int cost;
};
vector<muchie>muchii;
vector<muchie>sol;
int repr[105];
int cost_apm=0;

bool comp (muchie a, muchie b)
{
    return a.cost<b.cost;
}

int gasire(int x)
{
    if (x==repr[x])
        return x;
    repr[x]=gasire(repr[x]);
    return repr[x];
}

void unire(int x, int y)
{
    int rx=gasire(x);
    int ry=gasire(y);
    if (rx != ry)
    {
        repr[ry]=rx;
    }
}
int n,m,c1,c2,val;
int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>c1>>c2>>val;
        muchii.push_back({c1,c2,val});
    }
    for (int i=1;i<=n;i++)
        repr[i]=i;
    sort(muchii.begin(),muchii.end(),comp);
    for (int i=0;i<muchii.size();i++)
    {
        if (gasire(muchii[i].x) != gasire(muchii[i].y))
        {
            unire(muchii[i].x, muchii[i].y);
            cost_apm+=muchii[i].cost;
            sol.push_back({muchii[i].x,muchii[i].y,muchii[i].cost});
        }
    }
    cout<<cost_apm<<endl<<sol.size()<<endl;
    for (int i=0;i<sol.size();i++)
        cout<<sol[i].x<<' '<<sol[i].y<<endl;
    return 0;
}