#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define NMAX 400010

using namespace std;
struct muchie
{
    int x,y,cost;
};

muchie m[NMAX];
vector<int> sol;
int gr[NMAX];

bool compare(muchie a,muchie b)
{
    return a.cost < b.cost;
}
int grupa(int i)
{
    if(gr[i] == i) return i;
    return gr[i] = grupa(gr[i]);
}

void gr_union(int i,int j)
{
    gr[grupa(i)] = grupa(j);
}

int main()
{
    int i,n,M,apm=0;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d",&n,&M);
    for(i=0;i<M;i++)
        scanf("%d%d%d",&m[i].x,&m[i].y,&m[i].cost);

    sort(m,m+M,compare);
    for(i=1;i<=n;i++) gr[i] = i;

    for(i=0;i<M;i++)
    {
        if(grupa(m[i].x) != grupa(m[i].y))
        {
            apm+=m[i].cost;
            sol.push_back(i);
            gr_union(m[i].x, m[i].y);
        }
    }

    printf("%d\n%d\n",apm,sol.size());
    for(i=0;i<sol.size();i++)
        printf("%d %d\n",m[sol[i]].x,m[sol[i]].y);
}