#include <fstream>
#include<algorithm>

using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
int parent[200001],rang[200001],cost_min,muchii_apm,nr_parinte=200001,n,x1[200001],x2[200001];
struct nod
{
    int x,y,c;
}graf[400001];
int minim (int a , int b)
{
    if(a<b)
        return a;
    else
        return b;
}
bool comparator( nod i, nod j)
{
    return (i.c<j.c);
}
void change_rank( int p,int np)
{
    for(int i=1;i<=n;i++)
        if(parent[i]==p&&parent[i]!=0)
            parent[i]=np;
            if(nr_parinte>np&&np!=0)
                nr_parinte=np;
}
void union_sets(int i, int j)
{

    if(parent[i]==0&&parent[j]==0)
    {
        parent[i]=minim(i,j);
        parent[j]=minim(i,j);
    }
    else
    if(parent[i]<parent[j])
            {
               if(parent[i]>0)
                   change_rank(parent[j],parent[i]);

               else
                   parent[i]=parent[j];

            }
    else
    {
        if(parent[j]>0)
                change_rank(parent[i],parent[j]);
        else

            {
                parent[j]=parent[i];
            }
    }

}
int main()
{
    int m,i,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>graf[i].x>>graf[i].y>>graf[i].c;
    sort(graf+1,graf+m+1,comparator);

    for(i=1;i<=m;i++)
        {
            if(parent[graf[i].x]!=parent[graf[i].y]||(parent[graf[i].y]==0&&parent[graf[i].x]==0))
                {cost_min+=graf[i].c;
                union_sets(graf[i].x,graf[i].y);
                muchii_apm++;
                x1[muchii_apm]=graf[i].x;
                x2[muchii_apm]=graf[i].y;
                }
        }
        g<<cost_min<<'\n'<<muchii_apm<<'\n';
     for(i=1;i<=muchii_apm;i++)
        g<<x1[i]<<" "<<x2[i]<<'\n';
    return 0;
}