#include <stdio.h>
#include <vector>
#include <queue>
#define dim 200001

using namespace std;

struct vecin
{
    int nod;
    int cost;
};

struct muchie
{
    int nod1;
    int nod2;
    int cost;
};

struct compare: public binary_function <muchie, muchie, bool>
{
    bool operator() (muchie a, muchie b)
    {
        return (a.cost>b.cost);
    }
};

int n,m,sum,marked[dim];
vector <vecin> a[dim];
vector <muchie> b;
priority_queue <muchie,vector<muchie>,compare> h;

void prim()
{
    int count = 0;//muchi ales
    int nod = 0;//pornesc din nodu 0
    while (count < n-1)
    {
        marked[nod]=1;
        vector <vecin>::iterator i;
        for (i=a[nod].begin();i<a[nod].end();i++)
        {
            if (marked[(*i).nod]==0) //daca e nevizitat
            {
                muchie t;
                t.nod1 = nod;
                t.nod2 = (*i).nod;
                t.cost = (*i).cost;
                h.push(t);
            }
        }
        bool done = false;
        while(!done)
        {
            muchie t = h.top();
            nod = t.nod2; //posibil urm nod
            if (marked[t.nod2]==0)//nod valid
            {
                count++;
                sum+=t.cost;
                b.push_back(t);
                done = true;
            }
            h.pop();
        }
    }
}

int main()
{
    int i,x1,x2,c;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=0;i<m;i++)
    {
        vecin t;
        scanf("%d %d %d",&x1,&x2,&c);
        t.nod = x2-1;
        t.cost = c;
        a[x1-1].push_back(t);
        t.nod = x1-1;
        a[x2-1].push_back(t);
    }
    prim();
    printf("%d\n%d\n",sum,n-1);
    vector <muchie>::iterator j;
    for (j=b.begin();j<b.end();j++)
    {
        printf("%d %d\n",(*j).nod1+1,(*j).nod2+1);
    }
    return 0;
}