#include <fstream>
#include <vector>
#define NMAX 200004
#define MMAX 400004
#define INF 1000000

using namespace std;

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

int n, m;
struct vecin
{
    vector <int> vf;
    vector <double> cost;
};
vecin A[NMAX];
bool uz[NMAX];
int cmin[NMAX], prec[NMAX], Z[NMAX];
int start;
int cost_total;

void citire();
void initializare();
void prim();
void afisare();

int main()
{
    citire(); start=1;
    initializare();
    prim();
    afisare();
    return 0;
}

void citire()
{
    int i, x, y;
    double c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        A[x].vf.push_back(y); A[x].cost.push_back(c);
        A[y].vf.push_back(x); A[y].cost.push_back(c);
    }
}

void initializare()
{
    int i, j;
    int lg;
    for(i=1;i<=n;i++)
    {
        cmin[i]=INF; prec[i]=start;
        if(i==start)
        {
            cmin[i]=0;
            prec[i]=0;
        }
            else
            {
                lg=A[i].vf.size();
                for(j=0;j<lg;j++)
                    if(A[i].vf[j]==start)
                        if(cmin[i]>A[i].cost[j])
                            cmin[i]=A[i].cost[j];
            }
    }
}

void prim()
{
    int i, j, minim, lg;
    uz[start]=1; Z[1]=1;
    cmin[0]=INF;
    for(i=2;i<=n;i++)
    {
        minim=0;
        for(j=1;j<=n;j++)
            if(!uz[j]&&cmin[j]<cmin[minim])
                minim=j;

        Z[i]=minim;
        uz[minim]=1;
        cost_total+=cmin[minim];

        lg=A[minim].vf.size();
        for(j=0;j<lg;j++)
        {
            if(!uz[A[minim].vf[j]] && A[minim].cost[j]<cmin[j])
            {
                cmin[A[minim].vf[j]]=A[minim].cost[j];
                prec[A[minim].vf[j]]=minim;
            }
        }
    }
}

void afisare()
{
    int i;
    fout<<cost_total<<'\n'<<n-1<<'\n';
    for(i=1;i<=n;i++)
        if(prec[i])
            fout<<i<<' '<<prec[i]<<'\n';
}