#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct muchie
{
    int a,b,c;
} *heap;

vector <int> gf[400000],cst[400000],x,y;
void prim(int, int&);
int main()
{
    int a,b,c,n,m,C=0;
    ifstream fin("apm.in");
    fin>>n>>m;
    heap=new muchie[m];
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        gf[a].push_back(b); cst[b].push_back(c);
        gf[b].push_back(a); cst[a].push_back(c);
    }
    prim(n,C);
    ofstream fout("apm.out");
    fout<<C<<'\n';
    fout<<n-1<<'\n';
    for(unsigned int i=0;i<x.size();i++)
        fout<<x[i]<<' '<<y[i]<<'\n';
    return 0;
}

void intersh(int x,int y)
{
    muchie aux;
    aux=heap[x]; heap[x]=heap[y]; heap[y]=aux;
}

void urca(int nod)
{
    while(nod>1 && heap[nod/2].c>heap[nod].c)
    {
        intersh(nod/2,nod);
        nod=nod/2;
    }
}

void add(int x,int y,int cost,int &N)
{
    N++;
    heap[N].a=x; heap[N].b=y; heap[N].c=cost;
    urca(N);
}

void coboara(int nod,int &N)
{
    while((nod*2<=N && heap[nod*2].c<heap[nod].c) || ((nod*2)+1<=N && heap[(nod*2)+1].c<heap[nod].c))
        if((nod*2)+1<=N)
        {
            if(heap[nod*2].c<heap[(nod*2)+1].c)
            {
                intersh(nod*2,nod);
                nod=nod*2;
            }
            else
            {
                intersh((nod*2)+1,nod);
                nod=(nod*2)+1;
            }
        }
        else
            {
                intersh(nod*2,nod);
                nod=nod*2;
            }
}

void prim(int a, int &C)
{
    int *viz;
    viz=new int[a];
    for(int i=1; i<=a; i++)
        viz[i]=0;
    vector<int> nod;
    int nr,xi,yi,s;
    int N=0;
    viz[1]=1; nod.push_back(1);
    for(unsigned int i=0;i<gf[1].size();i++)
        add(1,gf[1][i],cst[1][i],N);
    nr=1;
    while(nr<a)
    {
        xi=heap[1].a; yi=heap[1].b; s=heap[1].c;
        while(viz[yi])
        {
            heap[1]=heap[N]; heap[N].a=0; heap[N].b=0; heap[N].c=0; N--;
            coboara(1,N);
            xi=heap[1].a; yi=heap[1].b; s=heap[1].c;
        }
        x.push_back(xi); y.push_back(yi);
        C+=s;
        heap[1]=heap[N]; heap[N].a=0; heap[N].b=0; heap[N].c=0; N--;
        coboara(1,N);
        viz[yi]=1;
        for(unsigned int i=0;i<gf[yi].size();i++)
            if(!viz[gf[yi][i]])
                add(yi,gf[yi][i],cst[yi][i],N);
        nr++;
    }
}