#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int tata[200050];
bool viz[200050];
struct muchii
{
    int a,b,c;
} v[400050];

int main()
{
    int x,y,minim,mini,i,j,nr=0,n,m,s=0,gasit=1,k,p,q;
    ifstream in ("apm.in");
    ofstream out ("apm.out");
    in>>n>>m;
    nr=0;
    for(i=1; i<=m; i++)
    {
        in>>v[i].a>>v[i].b>>v[i].c;
    }
    viz[v[1].a]=1;
    while(gasit==1)
    {
        gasit=0;
        mini=1001;
        for(i=1; i<=m; i++)
        {
            if(viz[v[i].a]==1 && viz[v[i].b]==0)
            {
                gasit=1;
                if(mini>v[i].c)
                {
                    mini=v[i].c;
                    k=v[i].b;
                    q=v[i].a;
                    p=i;
                }
            }
            else if(viz[v[i].b]==1 && viz[v[i].a]==0)
            {
                gasit=1;
                if(mini>v[i].c)
                {
                    mini=v[i].c;
                    k=v[i].a;
                    q=v[i].b;
                    p=i;
                }
            }
        }
        tata[k]=q;
        viz[k]=1;
        if(gasit==1)
            s+=v[p].c;
    }
   out<<s<<endl<<n-1<<endl;
   for(i=1; i<=n; i++)
    {
        if(tata[i]!=0)
            out<<i<<" "<<tata[i]<<endl;

    }
    return 0;
}