#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 200001
ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,i,j,gr[MAXN],cost,crt;
bool fol[MAXN];
struct grf
{
    int x,y,c;
}graf[MAXN];

bool cmp(grf a, grf b)
{
    return a.c<b.c;
}

int grupa(int nr)
{
    if(gr[nr]==nr)
        return nr;
    gr[nr]=grupa(gr[nr]);
    return gr[nr];
}

int reuniune(int a, int b)
{
    gr[grupa(a)] = grupa(b);
}
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
        cin>>graf[i].x>>graf[i].y>>graf[i].c;
    for(i=1; i<=n; i++)
        gr[i]=i;

    sort(graf+1,graf+m+1,cmp);

    for(i=1; i<=m; i++)
    {
        if(grupa(graf[i].x) != grupa(graf[i].y))
        {
            reuniune(graf[i].x, graf[i].y);
            cost+=graf[i].c;
            crt++; fol[i]=true;
        }
        if(crt==n-1)
            break;
    }
    cout<<cost<<"\n";
    cout<<n-1<<"\n";
    for(i=1; i<=m; i++)
        if(fol[i])
            cout<<graf[i].x<<" "<<graf[i].y<<"\n";
}