#include <fstream>
#include <vector>
#include <queue>
#define NMAX 200200
#define INF (1<<30)

using namespace std;

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

int n,m,total;
struct varf
{
    int x,c;
};
struct muchie
{
    int x,y,c;
    friend bool operator<(const muchie&m1,const muchie&m2);
};
bool operator<(const muchie&m1,const muchie&m2)
{
    return m1.c>m2.c;
}

vector <varf> G[NMAX];
priority_queue<muchie, vector<muchie> >H;
muchie a[NMAX];


bool uz[NMAX];
int cmin[NMAX];

void citire();
void prim();

int main()
{
    int i;

    citire();

    prim();

    fout<<total<<'\n'<<n-1<<'\n';
    for(i=1; i<n; i++)
        fout<<a[i].x<<' '<<a[i].y<<'\n';

    return 0;
}

void citire()
{
    int x,y,cost,i;
    varf p;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>cost;

        p.x=y; p.c=cost;
        G[x].push_back(p);

        p.x=x;
        G[y].push_back(p);
    }
}

void prim()
{
    int i,j,x,vf;
    muchie m,mm;

    ///initializare
    int start=1;
    uz[start]=1;

    for(i=1; i<=n; i++) cmin[i]=INF;
    cmin[start]=0;

    for(i=0; i<G[start].size(); i++)
    {
        m.y=start; m.x=G[start][i].x; m.c=G[start][i].c;
        H.push(m); cmin[m.x]=m.c;
    }

    for(i=1; i<n; )
    {
        m=H.top(); H.pop();

        if(uz[m.x]==0)
        {
            vf=m.x;
            total+=m.c; a[i]=m;
            uz[vf]=1; i++;
            for(j=0; j<G[vf].size(); j++)
                if(uz[G[vf][j].x]==0 && G[vf][j].c<cmin[G[vf][j].x])
                {
                    mm.x=G[vf][j].x; mm.y=vf; mm.c=G[vf][j].c;
                    H.push(mm); cmin[mm.x]=mm.c;
                }
                    continue;
        }
    }
}