#include <fstream>
#include <algorithm>
using namespace std;
struct boi
{
    int x,y,cost;
} v[400005],f[200005];
int tata[200005],cnt[200005];
bool mycmp(boi a,boi b)
{
    return a.cost<b.cost;
}

int find(int nod)
{
    while(nod!=tata[nod])
    {
        nod=tata[nod];
    }
    return nod;
}

bool verif(int nod1,int nod2)
{
    nod1=find(nod1),nod2=find(nod2);
    if(nod1!=nod2)
    {
        if(cnt[nod1]==cnt[nod2])
        {
            cnt[nod1]++;
        }
        if(cnt[nod1]<cnt[nod2])
            tata[nod1]=nod2;
        else
            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<n; i++)
    {
        cout<<f[i].x<<" "<<f[i].y<<"\n";
    }
    return 0;
}