#include <fstream>
#include <algorithm>
#define MMAX 200002
#define NMAX 400002

using namespace std;

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

int n, m;
struct Muchie
{
    int x, y;
    double c;
};
Muchie G[MMAX];

int APM[NMAX];
int conex[MMAX];
long double cost_APM;
int nrm;

void citire();
bool crit(Muchie, Muchie);

int main()
{
    citire();
    int i, j, c1, c2;
    for(i = 1; nrm <= n-1 ; ++i)
    {
        if( conex[G[i].x] != conex[G[i].y] )
        {
                if( conex[G[i].x]<conex[G[i].y] )
                {
                    c1 = conex[G[i].x];
                    c2 = conex[G[i].y];
                }
                else
                {
                    c1 = conex[G[i].y];
                    c2 = conex[G[i].x];
                }
                APM[++nrm] = i;
                cost_APM += G[i].c;
                for(j = 1; j<=n; ++j)
                    if( conex[j] == c2)
                        conex[j] = c1;
        }
    }

    fout<<cost_APM<<'\n'<<n-1<<'\n';
    for(i = 1; i<=n-1; ++i)
        fout<<G[APM[i]].y<<" "<<G[APM[i]].x<<'\n';
    return 0;
}

void citire()
{
    fin>>n>>m;
    int i;
    for(i = 1 ;i<=m; ++i)
        fin>>G[i].x>>G[i].y >>G[i].c;
    for(i = 1; i<=n; ++i)
        conex[i] = i;
    sort(G+1,G+m+1, crit);
    /*
    for(i = 1 ;i<=m; ++i)
        fout<<G[i].x<<" "<<G[i].y<<" "<<G[i].c<<"\n";
    */
}

bool crit(Muchie a, Muchie b)
{
    return (a.c < b.c);
}