#include <bits/stdc++.h>

using namespace std;

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

int n,m,x,y,xroot,yroot,pret,i,cost,sz,parinte[101],Rank[101];
vector <tuple<int,int,int>> v;
vector <pair<int,int>> muchii;

int radacina(int x)
{
    if(parinte[x] != x)
        parinte[x] = radacina(parinte[x]);
    return parinte[x];
}
void leaga(int x,int y)
{
    if(Rank[y] > Rank[x])
    {
        parinte[x] = y;
        Rank[y] += Rank[x];
    }
    else
    {
        parinte[y] = x;
        Rank[x] += Rank[y];
    }
}
bool cmp(tuple<int,int,int> a, tuple<int,int,int> b)
{
    return get<2>(a) < get<2>(b);
}
int main()
{
    f >> n >> m;
    while(m --)
    {
        f >> x >> y >> pret;
        v.push_back(make_tuple(x, y, pret));
    }
    for(i = 1; i <= n; ++ i)
    {
        parinte[i] = i;
        Rank[i] = 1;
    }
    sort(v.begin(), v.end(), cmp);
    i = 0;
    while(sz < n - 1)
    {
        x = get<0>(v[i]);
        y = get<1>(v[i]);
        xroot = radacina(x);
        yroot = radacina(y);
        if(xroot != yroot)
        {
            leaga(xroot,yroot);
            cost += get<2>(v[i]);
            ++ sz;
            muchii.push_back({x,y});
        }
        ++ i;
    }
    g << cost << '\n' << sz << '\n';
    for(i = 0; i < sz; ++ i)
        g << muchii[i].first << ' ' << muchii[i].second << '\n';

}