#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector < pair <int,int> > Sol;
const int NMAX=400001;
int N,M;
int S=0;
struct edge
{
    int x,y,c;
}E[NMAX];
int m[NMAX],sz[NMAX];
bool comp(edge A,edge B)
{
    return A.c<B.c;
}

void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;++i)
        fin>>E[i].x>>E[i].y>>E[i].c;
    sort(&E[1],&E[M+1],comp);
    for(int i=1;i<=NMAX;++i)m[i]=i,sz[i]=1;
}
int Find(int x)
{
    int root_x=x;
    int aux;
    while(m[root_x]!=root_x)
        root_x=m[root_x];
    while(m[x]!=root_x)
    {
        aux=m[x];
        m[x]=root_x;
        x=aux;
    }
    return root_x;
}
void Union(int x,int y)
{
    int root_x=Find(x);
    int root_y=Find(y);
    if(sz[root_x]<sz[root_y])
    {
        m[root_x]=root_y;
        sz[root_x]+=sz[root_y];
    }
    else
    {
        m[root_y]=root_x;
        sz[root_y]+=sz[root_x];
    }
}
void APM()
{
    int k=0;
    for(int i=1;i<=M && k<N;++i)
        {
            int X=Find(E[i].x);
            int Y=Find(E[i].y);
            if(X!=Y)
            {
                Union(X,Y);
                Sol.push_back(make_pair(E[i].x,E[i].y));
                S+=E[i].c;
                k++;
            }
        }
}
int main()
{
    Read();
    APM();
    fout<<S<<"\n";
        fout<<N-1<<"\n";
    for(int i=0;i<Sol.size();++i)
        fout<<Sol[i].first<<' '<<Sol[i].second<<'\n';
    return 0;
}