#include <algorithm>
#include <fstream>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

#define lim 200010
#define inf 2e9
int n,m,k;
struct nodd{int x,y,c;} ini[2*lim];
int dad[lim];
struct nodddd{int x,y;} sol[2*lim];

bool cmp (nodd A, nodd B)
{
    return A.c<B.c;
}

int get_dad (int nod)
{
    if (nod!=dad[nod])  dad[nod] = get_dad (dad[nod]);
    return dad[nod];
}

int main()
{
    int x,y,cost;
    fin>>n>>m;
    for (int i=1; i<=m; i++)
        fin>>ini[i].x>>ini[i].y>>ini[i].c;

    sort (ini+1, ini+m+1, cmp);
    for (int i=1; i<=n; i++)    dad[i]=i;

    long long rez=0;
    for (int i=1; i<=m; i++)
        if (get_dad(ini[i].x) != get_dad(ini[i].y))
        {
            rez+=ini[i].c;
            dad[get_dad(ini[i].x)] = get_dad(ini[i].y);
            sol[++k]={ini[i].x, ini[i].y};
        }

    fout<<rez<<'\n'<<k<<'\n';
    for (int i=1; i<=k; i++)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}