#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#define NX 200001
#define MX 400001
using namespace std;

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

struct muc
{
    int a,b,c;
};
int n,m;
muc v[MX];
int t[NX];
int total;
vector< pair<int, int> > sol;

bool comp(muc a, muc b)
{
    return a.c < b.c;
}

void citire()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>v[i].a>>v[i].b>>v[i].c;
    }

    for(i=1; i<=n; i++)
    {
        t[i] = i;
    }
}

int Find(int x)
{
    while(x != t[x]) x = t[x];
    return x;
}

void kruskal()
{
    int i,a,b,c,x,y;
    pair<int, int> e;
    for(i=1; i<=m; i++)
    {
        a = v[i].a;
        b = v[i].b;
        c = v[i].c;

        x = Find(a);
        y = Find(b);
        if(x != y)
        {
            t[x] = y;
            total += c;
            e.first = a;
            e.second = b;
            sol.push_back(e);
        }
    }
}

int main()
{
    pair<int, int> e;

    citire();

    sort(v+1, v+m+1, comp);
    kruskal();

    fout<<total<<'\n';
    fout<<sol.size()<<'\n';
    while(!sol.empty())
    {
        e = sol.back();
        sol.pop_back();
        fout<<e.first<<' '<<e.second<<'\n';
    }

    fin.close(); fout.close();
    return 0;
}