#include <fstream>
#include <algorithm>
#define NMAX 400400
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

long long sumcost;
int homany, N,M,mark[NMAX], howmany,ind,p,q;

struct chestie{
int x,y,cost;
}sol[NMAX], node[NMAX];
void scan();
void prev();
void print();
bool comp(chestie A, chestie B);
int main()
{
    scan();
    prev();
    sort(node+1,node+M+1, comp);
    howmany=0; ind=1;

    while(howmany<N)
    {
        do{
            p=mark[node[ind].x];
            q=mark[node[ind].y];
            if(p!=q)
                break;
            ++ind;
        }while(1 && ind<=M);

        if(ind<=M)
        {
        ++howmany;
        sol[howmany].x=node[ind].x;
        sol[howmany].y=node[ind].y;
        sumcost+=node[ind].cost;
         ++ind;
        for(int j=1; j<=N; ++j)
            if(mark[j]==p ||mark[j]==q)
                mark[j]=min(p,q);
        }
        else break;
    }

    print();

    return 0;
}

void scan()
{
    cin>>N>>M;
    for(int i=1; i<=M; ++i)
        cin>>node[i].x>>node[i].y>>node[i].cost;
}

void prev()
{
    for(int i=1; i<=N; ++i)
        mark[i]=i;
}

bool comp(chestie A, chestie B)
{
    return (A.cost<B.cost||(A.cost==B.cost && (A.x<B.x||(A.x==B.x&&A.y<B.y))));
}

void print()
{
    cout<<sumcost<<'\n'<<howmany<<'\n';
    for(int i=1; i<=howmany; ++i)
        cout<<sol[i].x<<' '<<sol[i].y<<'\n';
}