#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
struct muchie
{
   int x,y,c;
}u[1005],s[1005];
int n,m,k,i,cost,j,nr1,nr2;
int P[1005],nr;
bool Comp(muchie x,muchie y)
{
    if(x.c<y.c)
        return true;
return false;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>u[i].x>>u[i].y>>u[i].c;
        P[i]=i;
    }
    sort(u+1,u+m+1,Comp);
    int i=1;
    while(k<n-1)
    {
        if(P[u[i].x]!=P[u[i].y])
        {
            k++;
            cost=cost+u[i].c;
            s[k]=u[i];
            nr++;
            int n1=P[u[i].x];
            int n2=P[u[i].y];
            for(int j=1;j<=n;j++)
            {
                if(P[j]==n2)
                    P[j]=n1;
            }
        }
        i++;
    }
    g<<cost<<"\n";
    g<<nr<<"\n";
    for(int i=1;i<=k;i++)
        g<<s[i].x<<" "<<s[i].y<<"\n";

    return 0;
}