#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200002

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct ext{
    int s,d;
};

struct nod{
    int v1,v2,c;
};

int t[NMAX],r[NMAX],n,m;
vector <nod> mu;
vector <ext> sol;

bool cmp(nod A, nod B)
{
    return A.c<B.c;
}
int drum(int x)
{
    int r,y;
    r=x;
    while(r!=t[r])
        r=t[r];
    y=x;
    while(x!=t[x])
    {
        y=t[x];
        t[x]=r;
        x=y;
    }
}

void uneste(int x, int y)
{
    if(r[x]>r[y])
        t[y]=t[x];
    else
        t[x]=t[y];
    if(r[x]==r[y])
        r[y]++;
}
int main()
{
    int x,y,c,ct=0,nr=0;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        mu.push_back({x,y,c});
    }
    sort(mu.begin(), mu.end(), cmp);
    for(int i=1;i<=n;i++)
        t[i]=i,r[i]=1;
    for(int i=0;i<m;i++)
    {
        x=mu[i].v1;
        y=mu[i].v2;
        int cost=mu[i].c;
        int rx=drum(x);
        int ry=drum(y);
        if(rx!=ry)
        {
            nr++;
            ct+=cost;
            sol.push_back({x,y});
            uneste(rx,ry);
        }
    }
    g<<ct<<"\n"<<nr<<"\n";
    for(int i=0;i<nr;i++)
        g<<sol[i].d<<" "<<sol[i].s<<"\n";
    f.close(); g.close();
    return 0;
}