#include <fstream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

const string filename = "apm";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int NMAX = 2e5 + 5;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

vector<tiii> vtup;
vector<pii> apm;
int tree[NMAX], cost;

int getRoot(int node)
{
    if(tree[node] == node)
    {
        return node;
    }
    tree[node] = getRoot(tree[node]);
    return tree[node];
}

int main()
{
    int n, m;
    fin>>n>>m;

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

    while(m--)
    {
        int x,y,c;
        fin>>x>>y>>c;
        vtup.push_back(make_tuple(c, x, y));
    }

    sort(vtup.begin(), vtup.end());

    for(auto it : vtup)
    {
        int x, y, c, rootx, rooty;
        tie(c, x, y) = it;
        rootx = getRoot(x);
        rooty = getRoot(y);
        if(rootx != rooty)
        {
            cost += c;
            apm.push_back(make_pair(x, y));
            tree[rootx] = rooty;
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(auto it : apm)
    {
        fout<<it.first<<" "<<it.second<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}