#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int NMax = 200005,MMax = 400005;

struct Muchie
{
  int x,y,cost;

};

bool operator< (Muchie A,Muchie B)
    {
        return A.cost<B.cost;
    }

vector < pair <int, int> > Sol;
Muchie E[MMax];
int N,M,T[NMax],Sum;

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

void Unite(int x, int y)
{
    T[x] = y;
}

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


void Solve()
{
    for(int i = 1; i<=M; i++)
        {
            if(Father(E[i].x)!=Father(E[i].y))
                {
                    Sum += E[i].cost ;
                    Unite(Father(E[i].x),Father(E[i].y));
                    Sol.push_back(make_pair( E[i].x, E[i].y  ));
                }

        }
}

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

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