#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
typedef pair<int, int> pr;
typedef pair<pr,  int> nod;

const int N_MAX=200011;
const int oo=1<<29;

vector<nod> G;
vector<pr> apm;

namespace std {
    inline istream& operator>>(istream& in, nod& x)
    {
        in>>x.first.first>>x.first.second>>x.second;
        return in;
    }
    inline ostream& operator<<(ostream& out, const pr& x) {out<<x.first<<' '<<x.second; return out;}
    inline bool operator<(const nod& x, const nod& y) {return x.second < y.second;}
};
int f[N_MAX], r[N_MAX];

int find(int x)
{
    int y, z;

    for(y=x; y != f[y]; y=f[y]);
    while(x != f[x])
    {
        z=f[x];
        f[x]=y;
        x=z;
    }
    return y;
}
inline void unite(int x, int y)
{
    if(r[x] == r[y])
    {
        if(x != y)
            f[x]=f[y];
        ++r[x];
    }
    else r[x]=r[y]= r[x] <= r[y] ? r[x] : r[y];
}

int main()
{
    int N, M, i, j, s, fx, fy;
    ifstream in("apm.in");
    ofstream out("apm.out");

    in>>N>>M;
    copy(istream_iterator<nod>(in), istream_iterator<nod>(), back_inserter(G));
    sort(G.begin(), G.end());
    for(i=1; i <= N; ++i)
        f[i]=i, r[i]=1;
    N-=1;
    for(i=0, j=s=0; i < M; ++i)
    {
        fx=find(G[i].first.first);
        fy=find(G[i].first.second);
        if(fx != fy)
        {
            s+=G[i].second;
            unite(fx, fy);
            apm.push_back(G[i].first);
            ++j;
        }
        if(j >= N)
            break;
    }
    out<<s<<'\n'<<j<<'\n';
    copy(apm.begin(), apm.end(), ostream_iterator<pr>(out, "\n"));

    return EXIT_SUCCESS;
}