#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 200001

using namespace std;
int dad[MAX];

int find_daddy(int x)
{
    if(dad[x] == x)return x;
    return dad[x]=find_daddy(dad[x]);
}

inline void join(int x, int y)
{
    int rx = find_daddy(x);
    int ry = find_daddy(y);

    dad[ry] = rx;
}

bool check(int x, int y)
{
    return find_daddy(x) != find_daddy(y);
}

struct edge
{
    int n1, n2, cost;
};
edge v[MAX];

bool cmp(edge A, edge B)
{
    return A.cost < B.cost;
}
vector<int> sol;
int main()
{
    int n, m, a, b, cost = 0, i;

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

    fin >> n >> m;

    for(i = 1; i <= m; i++)fin >> v[i].n1 >> v[i].n2 >> v[i].cost;

    sort(v + 1, v + m + 1, cmp);

    for(i = 1; i <= n; i++)dad[i] = i;
    for(i = 1; sol.size() < n - 1; i++)
    {
        if(check(v[i].n1, v[i].n2))
        {
           // cout << "ASDASDASD";
            sol.push_back(i);
            cost += v[i].cost;
            join(v[i].n1, v[i].n2);
        }
       //cout << i << sol.size() << endl;
    }

    fout << cost << '\n' << n - 1 << '\n';

    for(auto x : sol)
        fout << v[x].n2 << " " << v[x].n1 << '\n';

    fin.close();
    fout.close();

    return 0;
}