#include <fstream>
#include <vector>
#include <bitset>
#include <map>

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

struct Node
{
    int dat;
    int rnk;
    Node *par;
};

vector <Node> v;

void makeSet(int dat)
{
    v[dat].dat = dat;
    v[dat].rnk = 0;
    v[dat].par = &v[dat];
}

Node* findPar(Node *node)
{
    if(node->par == node)
        return node;

    Node *par = findPar(node->par);
    node->par = par;
    return par;
}

int findPar(int dat)
{
    return findPar(&v[dat])->par->dat;
}

void unionSet(Node *node1, Node *node2)
{
    Node *par1 = findPar(node1);
    Node *par2 = findPar(node2);

    if(par1 == par2)
        return;

    if(par1->rnk >= par2->rnk)
    {
        par2->par = par1;

        if(par1->rnk == par2->rnk)
            ++par1->rnk;
    }
    else
        par1->par = par2;
}

void unionSet(int node1, int node2)
{
    unionSet(&v[node1], &v[node2]);
}

int sum, nrsol, a[400005], b[400005];
multimap <int, int> edges;
bitset <400005> sol;
int main()
{
    int n, m;
    cin >> n >> m;

    v.resize(n + 1);

    for(int i = 1; i <= n; ++i)
        makeSet(i);

    for(int i = 1; i <= m; ++i)
    {
        int c;
        cin >> a[i] >> b[i] >> c;
        edges.insert({c, i});
    }

    for(auto it = edges.begin(); it != edges.end(); ++it)
    {
        int x = it->second;

        if(findPar(a[x]) != findPar(b[x]))
        {
            unionSet(a[x], b[x]);
            sum += it->first;
            ++nrsol;
            sol[x] = true;
        }
    }

    cout << sum << '\n' << nrsol << '\n';

    for(int i = 1; i <= m; ++i)
    {
        if(sol[i] == true)
            cout << a[i] << ' ' << b[i] << '\n';
    }

    return 0;
}