#include <iostream>
#include <fstream>

#define dim 200005

using namespace std;

const int inf = 2000000000; ///infinit

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

struct rezultat
{
    int x,y;
}out[dim];

int outsize;

struct graf
{
    int nod,len;
    graf* next;
}*a[dim];

int N,n,m,H[dim],d[dim],poz[dim],sol[dim],dimsol,tata[dim];

inline int father(int nod)
{
    return nod / 2;
}

inline int left_son(int nod)
{
    return nod * 2;
}

inline int right_son(int nod)
{
    return nod * 2 + 1;
}

inline int mini_heap()
{
    return H[1];
}

void sift(int K)
{
    int son;
    do
    {
        son = 0;
        if (left_son(K) <= N)
        {
            son = left_son(K);
            if (right_son(K) <= N && d[H[right_son(K)]] < d[H[left_son(K)]])
            {
                son = right_son(K);
            }
            if (d[H[son]] >= d[H[K]])
            {
                son = 0;
            }
        }
        
        if (son)
        {
            poz[H[K]]=son;
            poz[H[son]]=K;
            swap(H[K], H[son]);
            K = son;
        }
    }
    while (son);
}

void percolate(int K)
{
    int key = H[K];
    
    while ((K > 1) && (d[key] < d[H[father(K)]]))
    {
        H[K] = H[father(K)];
        poz[H[father(K)]] = K;
        K = father(K);
    }
    
    H[K] = key;
    poz[H[K]] = K;
}

void cut(int K)
{
    H[K] = H[N];
    poz[H[N]] = K;
    --N;
    
    if ((K > 1) && (d[H[K]] > d[H[father(K)]]))
    {
        percolate(K);
    }
    else
    {
        sift(K);
    }
}

void heapinsert(int key) {
    H[++N] = key;
    poz[key]=N;
    percolate(N);
}

void build_heap()
{
    for (int i = N / 2; i > 0; --i)
    {
        sift(i);
    }
}

void addinsol(int nod)
{
    sol[dimsol++]=nod;
    graf* j=a[nod];
    while (j!=NULL)
    {
        if (d[j->nod]==inf)
        {
            d[j->nod]=j->len;
            tata[j->nod]=nod;
            heapinsert(j->nod);
        }
        else if (j->len<d[j->nod])
        {
            d[j->nod]=j->len;
            tata[j->nod]=nod;
            percolate(poz[j->nod]);
        }
        j=j->next;
    }
}

int main()
{
    int sum=0;
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        graf* nou=new graf;
        nou->nod=y;
        nou->len=cost;
        nou->next=a[x];
        a[x]=nou;
        nou=new graf;
        nou->nod=x;
        nou->len=cost;
        nou->next=a[y];
        a[y]=nou;
    }
    for (int i=2;i<=n;i++)
        d[i]=inf;
    addinsol(1);
    while (N)
    {
        int nod=mini_heap();
        sol[dimsol++]=nod;
        sum+=d[nod];
        out[outsize].x=tata[nod];
        out[outsize].y=nod;
        outsize++;
        cut(1);
        addinsol(nod);
    }
    fout<<sum<<'\n'<<outsize<<'\n';
    for (int i=0;i<outsize;i++)
        fout<<out[i].x<<' '<<out[i].y<<'\n';
    return 0;
}