#include <cstdio>
#include <vector>
#include <algorithm>

#define Nmax 200005
using namespace std;
vector<pair<int,pair<int,int> > > edges;
vector<pair<int,int> > sol;
int daddy[Nmax],N,M;
int whos_ur_daddy(int k){
    if(daddy[k] != k)
        daddy[k] = whos_ur_daddy(daddy[k]);
    return daddy[k];
}

void Read()
{
    scanf("%d%d",&N,&M);
    int a,b,c;
    for(int i = 1; i <= M; ++i){
        scanf("%d%d%d",&a,&b,&c);
        edges.push_back(make_pair(c,make_pair(a,b)));
    }
    for(int i = 1; i <= N; ++i)
            daddy[i] = i;
}

void couple(int a,int b)
{
    daddy[daddy[a]] = daddy[b];
}

void Solve()
{
    sort(edges.begin(),edges.end());
    int a,b,c;
    int total = 0;
    for(vector<pair<int, pair<int,int> > >::iterator it = edges.begin(); it != edges.end(); ++it)
    {
        a = it->second.first;
        b = it->second.second;
        c = it->first;
        if(whos_ur_daddy(a) == whos_ur_daddy(b))
            continue;
        couple(whos_ur_daddy(a),whos_ur_daddy(b));
        total += c;
        sol.push_back(make_pair(a,b));
    }
    printf("%d\n",total);
    printf("%d\n",sol.size());
    for(vector<pair<int,int> >::iterator it = sol.begin(); it != sol.end();++it)
        printf("%d %d\n",it->first,it->second);

}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    Read();
    Solve();

    return 0;
}