#include<string.h>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
struct Hirohito{int x,y,c;}cost[400001];
struct Hindenburg{unsigned int x,y;}mu[200001];
unsigned int t[200001],n,m,nrc[200001];
int radacina(int i)
{
    int k = i;
    while(t[k])
        k = t[k];
    while(t[i])
    {
        t[i] = k;
        i = t[i];
    }
    return k;
}

void ONU(int i, int j)
{
    if(nrc[i] > nrc [j])
    {
        nrc [i] += nrc[j];
        t[j] = i;
    }
    else
    {
        nrc[j] += nrc[i];
        t[i] = j;
    }
}

bool sortare(const Hirohito a,const Hirohito b)
{
    return a.c < b.c;
}

int main()
{
    int i,nr = 0,loc = 0,nod = 0,ri,rj;
    f>>n>>m;
    for(i = 1; i <= m; i ++)
    f>>cost[i].x>>cost[i].y>>cost[i].c;
    sort(cost + 1, cost + m + 1, sortare);
    memset(nrc,1,n);
    for(i = 1; i <= m && nod <= n - 1; i ++)
    {
        ri = radacina(cost[i].x);
        rj = radacina(cost[i].y);
        if(ri != rj)
        {
            ONU(ri,rj);
            nod ++;
            nr = nr + cost[i].c;
            mu[nod].x = cost[i].x;
            mu[nod].y = cost[i].y;
        }
    }
    g<<nr<<'\n'<<nod<<'\n';
    for(i = 1; i <= nod; i ++)
    g<<mu[i].x<<" "<<mu[i].y<<'\n';


}