#include <iostream>
#include <fstream>
using namespace std;
struct muchie
{
    int u,v,w;
};
#define DIM 500001
muchie x[DIM],sol[DIM];
int n,m,t[DIM],s,cnt;
int partitie(int st,int dr)
{
    int pivot=x[dr].w,i=st;
    for(int j=st;j<dr;j++)
    {
        if(x[j].w<pivot)
        {
            swap(x[j].w,x[i].w);
            swap(x[j].u,x[i].u);
            swap(x[j].v,x[i].v);
            i++;
        }
    }
    swap(x[dr].w,x[i].w);
    swap(x[dr].u,x[i].u);
    swap(x[dr].v,x[i].v);
    return i;
}
void quicksort(int st,int dr)
{
    if(st<dr)
    {
        int k=partitie(st,dr);
        quicksort(st,k-1);
        quicksort(k+1,dr);
    }
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        fin>>x[i].u>>x[i].v>>x[i].w;
    }
    quicksort(0,m-1);
    for(int i=1;i<=n;i++)
    {
        t[i]=i;
    }
    for(int i=0;i<m && cnt<n;i++)
    {
        if(t[x[i].u]!=t[x[i].v])
        {
            s+=x[i].w;
            sol[cnt].u=x[i].u;
            sol[cnt].v=x[i].v;
            cnt++;
            int ai=t[x[i].u],aj=t[x[i].v];
            for(int j=1;j<=n;j++)
            {
                if(t[j]==aj)
                {
                    t[j]=ai;
                }
            }
        }
    }
    fout<<s<<'\n'<<cnt<<'\n';
    for(int i=0;i<cnt;i++)
    {
        fout<<sol[i].u<<" "<<sol[i].v<<'\n';
    }
}