#include <iostream>
#include <fstream>
using namespace std;

ofstream fout ("apm.out");

struct muchie
{
    int e1, e2;
    int cost;
};

muchie G[200002], apm[200002];
int T[200002], H[200002], n, m, costapm=0;

void creare()
{
    ifstream fin ("apm.in");
    fin >> n >> m;
    for(int i=1;i<=m;i++)
        fin >> G[i].e1 >> G[i].e2 >> G[i].cost;
    fin.close();
}

int detroot(int x)
{
    if(T[x]==0)
        return x;
    else
        return detroot(T[x]);
}

int pmin(int i, int m)
{
    if(i>m/2)
        return -1;
    if(2*i+1>m)
        return 2*i;
    else
    {
        if(G[2*i].cost<G[2*i+1].cost)
            return 2*i;
        else
            return 2*i+1;
    }
}

void down(int i, int m)
{
    if(i>m/2)
        return;
    else
    {
        int p=pmin(i, m);
        if(G[i].cost>G[p].cost)
        {
            swap(G[i], G[p]);
            down(p, m);
        }
    }
}

void recHeap(int & m)
{
    swap(G[1], G[m]);
    m--;
    for(int i=m/2;i>=1;i--)
        down(i, m);
}

void afisare()
{
    fout << costapm << '\n';
    fout << n-1 << '\n';
    for(int i=1;i<=n-1;i++)
    {
        fout << apm[i].e1 << " " << apm[i].e2 << '\n';
    }
}

void test(int m)
{
    for(int i=1;i<=m;i++)
        cout << G[i].cost << " ";
    cout << endl;
}

int main()
{
    creare();
    int j=1, m2=m;
    for(int i=m/2;i>=1;i--)
        down(i, m);
    //test(m2);
    while(j<n)
    {
        int x=G[1].e1;
        int y=G[1].e2;
        int r1=detroot(x);
        int r2=detroot(y);
        if(r1!=r2)
        {
            apm[j++]=G[1];
            costapm+=G[1].cost;
            if(H[r1]>H[r2])
                T[r2]=r1;
            else if(H[r2]>H[r1])
                T[r1]=r2;
            else
            {
                T[r2]=r1;
                H[r1]++;
            }
        }
        recHeap(m2);
        //test(m2);
    }
    afisare();
    return 0;
}