using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
#define L ((i)*2)
#define R ((L)+1)
#define T ((i)/2)
#define nmax 200005
#define oo 0x3f3f3f3f

struct nod{
int lg,c;
};
vector<nod> G[nmax];
struct edge{
int x,y;};
vector<edge> lis;
ofstream fout("apm.out");

int N,M;
int v[nmax],H[nmax],ante[nmax],poz[nmax],nh;
void upheap(int i)
{
    if(i<=1) return;
    if(v[H[i]]<v[H[T]]) {swap(H[i],H[T]), swap(poz[H[i]], poz[H[T]]), upheap(T);}

}

void downheap(int i)
{
    int m=i;
    if(L<=nh)
    {
        if(v[H[L]]<v[H[m]])
            m=L;
    }
    if(R<=nh)
    {
        if(v[H[R]]<v[H[m]])
            m=R;

    }
    if(m!=i) {swap(H[m],H[i]), swap(poz[H[i]],poz[H[m]]), downheap(m);}
}

void solve()
{    int sum=0,u;
    nh=N;
    vector<nod>::iterator it;
    int i;
    for(i=1;i<=N;i++)
    {
        u=H[1];
        swap(H[1],H[nh]);
        swap(poz[H[1]],poz[H[nh]]);
        nh--;
        downheap(poz[H[1]]);
        poz[u]=0;
        sum+=v[u];
        lis.pb((edge){u,ante[u]});
        for(it=G[u].begin();it<G[u].end();it++)
        {
            if(poz[it->lg]>0)
            if(v[it->lg]>it->c)
            {
                v[it->lg]=it->c;
                ante[it->lg]=u;
                upheap(poz[it->lg]);
            }
        }

    }
    fout<<sum<<"\n";
    fout<<N-1<<"\n";
    for(i=1;i<lis.size();i++)
    {
        fout<<lis[i].x<<" "<<lis[i].y<<"\n";
    }

}

void init()
{   int i;
    H[1]=1;
    poz[1]=1;
    v[1]=0;

    for(i=2;i<=N;i++)
    {
        H[i]=i;
        poz[i]=i;
        v[i]=oo;
    }
}

void cit()
{   int i,x,y,z;
    ifstream fin("apm.in");

    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>z;
        G[x].pb((nod){y,z});
        G[y].pb((nod){x,z});
    }

    fin.close();
}

int main()
{

    cit();

    init();
    solve();
    fout.close();
    return 0;
}