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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int N = 200005;
const int inf = 1000000007;
int pset[N], m, n;
vector < pair <int, pair<int,int> > > edge;
vector < pair <int, int> > pairs;
void init ()
{
    for(int i=1; i<=n; i++)
        pset[i] = i;
}
int findSet (int u)
{
    if (pset[u] == u)
        return u;
    else
        return pset[u] = findSet(pset[u]);
}
int isSameSet (int u, int v)
{
    return findSet(u) == findSet(v);
}
void unionSet (int u, int v)
{
    pset[findSet(u)] = findSet(v);
}
int main ()
{
    f>>n>>m;
    for (int i=1; i<=m; i++)
    {
        int u, v, w;
        f>>u>>v>>w;
        edge.push_back(make_pair (w, make_pair(u, v)));
    }
    sort(edge.begin(), edge.end());
    init();
    long long ans = 0;

    for (__typeof(edge.begin()) it=edge.begin(); it != edge.end(); it++)
    {
        pair <int, int> e = it->second; //muchiile
        if(isSameSet(e.first, e.second))
            continue;
        unionSet(e.first, e.second);
        ans += it->first;
        pairs.push_back(make_pair(e.first, e.second));
    }
    g<<ans<<endl;
    g<<n-1<<endl;
    for (__typeof(pairs.begin()) it=pairs.begin(); it != pairs.end(); it++)
        g<<it->second<<" "<<it->first<<endl;//        <<" "<<*it.second<<endl;
}