#include <fstream>
#include <algorithm>
#define N 400004
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x, y, c;
}G[N];
 
int r[N], rang[N], sol[N];
int cost, muchii, Rx, Ry, n, m;
 
bool conditie(muchie x, muchie y)
{
    return (x.c<y.c);
}
 
int root(int x)
{
    while(r[x])
        x=r[x];
    return x;
}
void algoritm()
{
    for(int i=1; i<=n; i++)
        rang[i]=1;
    for(int i=1; i<=m && muchii<n-1; i++)
    {
        Rx=root(G[i].x);
        Ry=root(G[i].y);
        if(Rx!=Ry)
        {
            cost+=G[i].c;
            sol[++muchii]=i;
 
            if(rang[Rx]>rang[Ry])
            {
                rang[Rx]=rang[Rx]+rang[Ry];
                r[Ry]=Rx;
            }
            else
            {
                rang[Ry]=rang[Ry]+rang[Rx];
                r[Rx]=Ry;
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>G[i].x>>G[i].y>>G[i].c;
    sort(G+1, G+1+m, conditie);
    algoritm();
    fout<<cost<<endl<<n-1<<endl;
    for(int i=1; i<n; i++)
        fout<<G[sol[i]].x <<" "<<G[sol[i]].y<<" "<<endl;
    return 0;
}