#include <fstream>
#include <algorithm>
using namespace std;
struct muchie
{
    int x,y,c;
}u[400002];
int viz[200002];
int compare(muchie a,muchie b)
{
    if(a.c<b.c)
        return 1;
    return 0;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,m,i,j,cost,k,s[200002];
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>u[i].x>>u[i].y>>u[i].c;
    }
    sort(u+1,u+m+1,compare);
    viz[u[1].x]=1; viz[u[1].y]=1;
    cost=u[1].c;
    s[1]=1;
    for(k=2;k<=n-1;k++)
    {
        for(i=1;i<=m;i++)
        {
            if(viz[u[i].x]==1 and viz[u[i].y]==0)
            {
                viz[u[i].y]=1;
                cost=cost+u[i].c;
                s[k]=i;
                break;
            }
            else if(viz[u[i].x]==0 and viz[u[i].y]==1)
            {
                viz[u[i].x]=1;
                cost=cost+u[i].c;
                s[k]=i;
                break;
            }
        }
    }
    g<<cost<<endl<<n-1<<endl;
    for(i=1;i<=n-1;i++)
    {
        g<<u[s[i]].x<<' '<<u[s[i]].y<<endl;
    }
}