#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct lista
{
    int x;
    int y;
    int dist;

} a[200000];
int parent[1000];

bool cmp(lista p,lista q)
{
    if (p.dist<q.dist)
        return true;
    return false;
}

int parinte(int n)
{
    if (n==parent[n])
        return n;
    return parent[n]=parinte(parent[n]);
}

int main ()
{
    int n,k,u=0;
    f>>n>>k;

    for(int i=0;i<1000;i++)
        parent[i]=i;
    for(int i=1;i<=k;i++)
    {
        int x1,y1,c;
        f>>x1>>y1>>c;

        a[u].x=x1;
        a[u].y=y1;
        a[u].dist=c;
        u++;
    }

    sort(a,a+u,cmp);

    int cost=0,crt=n-1,count=0,aa[200000],bb[200000];

    for(int i=0;i<u && crt;i++)
    {
        int p=parinte(a[i].x);
        int q=parinte(a[i].y);
        if(p!=q)
        {
            parent[p]=q;
            aa[++count]=q;
            bb[count]=p;
            crt--;
            cost+=a[i].dist;
        }
    }

    g<<cost<<"\n"<<count<<"\n";
    for(int i=1;i<=count;i++)
        g<<aa[i]<<" "<<bb[i]<<"\n";

    f.close();
    g.close();
    return 0;
}