#include <fstream>
#include <vector>
#include <climits>

using namespace std;
int n, m, nrv, x, y, i, j, z, viz[200000];

ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct Muchie
{
   int e1, e2;
};

struct vecin
{
    int e1;
    int cost;
};

vector <vecin> G[200000];
vector <Muchie> L;

void citire()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
        G[y].push_back({x, z});
    }
}



int apm(int nod)
{
    nrv=n-1;
    viz[nod]=1;
    int costmin=0, mini, p1, p2;
    while(nrv>0)
    {
        mini=INT_MAX;
        for(i=1;i<=n;i++)
        {
            if(viz[i]==0)
            {
                for(j=0;j<G[i].size();j++)
                {
                    if(viz[G[i][j].e1]==1 && G[i][j].cost < mini)
                    {
                        mini=G[i][j].cost;
                        p1=i;
                        p2=G[i][j].e1;
                    }
                }
            }
        }
        costmin+=mini;
        L.push_back({p1, p2});
        viz[p1]=1;
        nrv--;
    }
    return costmin;
}

int main()
{
    citire();
    int nrmuchi=n-1;
    fout << apm(1) << '\n';
    fout << nrmuchi  << '\n';
    for(i=0;i<L.size();i++)
    {
        fout << L[i].e1 << " " << L[i].e2 << '\n';
    }
    return 0;
}