#include <fstream>
#include <vector>
#define NMAX 200002
#define INF 1000000000
using namespace std;

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

struct varf
{
    int x,c;
};
vector<varf> G[NMAX];
///G[i]=lista de adiac a varfului i(vector din STL)
bool uz[NMAX];
int cmin[NMAX];
int tata[NMAX];
int n,m,cost;
void citire();
int prim();
void afisare();
int main()
{
    citire();
    cost=prim();
    afisare();
    return 0;
}
void citire()
{
    int i,j,k,c;
    varf v;
    fin>>n>>m;
    for(k=0; k<m; k++)
    {
        fin>>i>>j>>c;
        v.x=j;
        v.c=c;
        G[i].push_back(v);
        v.x=i;
        G[j].push_back(v);
    }
    uz[1]=1;
    for(i=2; i<=n; i++)
    {
        tata[i]=1;
        cmin[i]=INF;
    }
    ///parcurg lista de adiacenta a lui 1
    for(i=0;i<G[1].size();i++)
        cmin[G[1][i].x]=G[1][i].c;

}
int prim()
{
    int nr=1,i,vf,vfmin,minim,cost=0;
    while(nr<n)
    {
        ///determin un varf neselectat aflat la cost minim de cele deja selectate
        minim=INF;
        for(i=1;i<=n;i++)
        if(!uz[i] && cmin[i]<minim)
        {
            minim=cmin[i];
            vfmin=i;
        }
        ///selectez vfmin
        uz[vfmin]=1;
        nr++;
        cost=cost+cmin[vfmin];
        ///actualizez eventual cmin datorita lui vfmin
        for(i=0;i<G[vfmin].size();i++)
        {
            vf=G[vfmin][i].x;
            if(!uz[vf] && cmin[vf]>G[vfmin][i].c)
                {cmin[vf]=G[vfmin][i].c;
                tata[vf]=vfmin;
                }
        }

    }
    return cost;
}
void afisare()
{
    int i;
    fout<<cost<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<' '<<tata[i]<<'\n';

}