#include <fstream>
#include <vector>
using namespace std;

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

int n, m, c[200010], ind, val, a[200010];
vector <pair <int, int>> v[200010];
vector <pair <int, int>> x;

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        f>>x>>y>>c;
        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }
    c[++ind]=1;
    a[0]=1;
    a[1]=1;
    while(ind<n)
    {
        int Min=2e9;
        int ini=0, urm=0;
        for(int i=1; i<=ind; i++)
        {
            for(int j=0; j<v[c[i]].size(); j++)
            {
                int vecin=v[c[i]][j].first;
                int cost=v[c[i]][j].second;
                if(cost < Min && (a[vecin]==0 || a[c[i]]==0))
                {
                    Min=cost;
                    ini=c[i];
                    urm=vecin;
                }
            }
        }
        val+=Min;
        x.push_back(make_pair(ini, urm));
        c[++ind]=urm;
        a[urm]=1;
        a[ini]=1;
    }
    g<<val<<'\n';
    g<<ind<<'\n';
    for(int i=0; i<ind-1; i++)
        g<<x[i].first<<" "<<x[i].second<<'\n';
    return 0;
}