#include <fstream>
#include <vector>
#include <algorithm>
#define NMax 200005
#define MMax 400005
using namespace std;

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

struct Muchie
{
    int x,y,c;
};
int TT[NMax];
Muchie V[MMax];
vector < pair<int, int> > Sol;

int N,M,Cost;
int RG[NMax];

bool Compare(Muchie A, Muchie B)
{
    return A.c<B.c;
}

void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
        {
            fin>>V[i].x>>V[i].y>>V[i].c;
        }
    sort(V+1, V+M+1,Compare);
}

int Father(int x)
{
    while(TT[x]!=x)
        x=TT[x];
    return x;
}

void Unite(int x, int y)
{
    if(RG[y]>RG[x])
        TT[x]=y; // y va fi radacina
    if(RG[x]>RG[y])
        TT[y]=x; // x va fi radacina
    if(RG[x]==RG[y])
        {
            TT[x] = y;
            RG[y]++;
        }
}

void Solve()
{
    int i,x1,y1;

    for(i=1;i<=NMax;i++)
        TT[i]=i;

    for(i=1; i<=M; i++)
        {
            x1=Father(V[i].x);
            y1=Father(V[i].y);
            if(x1!=y1)
                {
                    Cost += V[i].c;
                    Unite(x1, y1);
                    Sol.push_back(make_pair(V[i].y, V[i].x));
                }
        }
}

void Print()
{
    fout<<Cost<<"\n";
    fout<<N-1<<"\n";
    for(int i=0; i<(int)Sol.size(); i++)
        fout<<Sol[i].first<<" "<<Sol[i].second<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}