#include <fstream>
#include <algorithm>
using namespace std;
struct boi
{
    int x,y,cost;
} v[400005],f[200005];
int tata[200005];
bool mycmp(boi a,boi b)
{
    return a.cost<b.cost;
}
bool verif(int nod1,int nod2)
{
    int cpn1=nod1,cpn2=nod2;
    while(nod1!=tata[nod1])
    {
        nod1=tata[nod1];
    }
    while(nod2!=tata[nod2])
    {
        nod2=tata[nod2];
    }
    if(nod1!=nod2)
    {
        tata[nod2]=nod1;
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m,sum=0;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,mycmp);
    for(int i=1; i<=n; i++)
        tata[i]=i;
    int k=0;
    for(int i=1; i<=m; i++)
    {
        if(verif(v[i].x,v[i].y)==1)
        {
             sum+=v[i].cost;
             f[++k].x=v[i].x;
             f[k].y=v[i].y;
        }
    }
    cout<<sum<<"\n"<<n-1<<"\n";
    for(int i=1;i<=k;i++)
    {
        cout<<f[i].x<<" "<<f[i].y<<"\n";
    }
    return 0;
}