#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,i,cost,t[200001],h[200001],a,b;
vector<pair<int,int> > r;
struct edge
{
    int x,y,c;
}e[400001];
bool cmp(edge a,edge b)
{
    return a.c<=b.c;
}
int arb(int n)
{
    while (t[n]) n=t[n];
    return n;
}
void kruskal()
{
    int i,j=0;
    for (i=1;i<n;i++)
    {
        while (true)
        {
            j++;
            a=arb(e[j].x);
            b=arb(e[j].y);
            if (a!=b) break;
        }
        r.push_back(make_pair(e[j].x,e[j].y));
        cost+=e[j].c;

        if (h[a]>h[b]) t[b]=a;
        else if (h[a]<h[b]) t[a]=b;
        else
        {
            h[a]++;
            t[b]=a;
        }
    }
}
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
        scanf("%i%i%i",&e[i].x,&e[i].y,&e[i].c);
    sort(e+1,e+m+1,cmp);

    kruskal();

    printf("%i\n%i\n",cost,n-1);
    for (i=0;i<r.size();i++)
        printf("%i %i\n",r[i].first,r[i].second);
    fclose(stdin);
    fclose(stdout);
    return 0;
}