#include <cstdio>
#include <algorithm>
#include <queue>

#define Nmax 200005

using namespace std;
int N,M,daddy[Nmax];
priority_queue<pair<int,pair<int,int> > ,
        vector<pair<int,pair<int,int> > >,
       greater<pair<int,pair<int,int> > > > Q;
vector<pair<int,int> > sol;

int whos_ur_daddy(int k)
{
    if(daddy[k] != k)
        daddy[k] = whos_ur_daddy(daddy[k]);
    return daddy[k];
}
void couple(int a,int b)
{
    daddy[daddy[a]] = daddy[b];
}

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);
        Q.push(make_pair(c,make_pair(a,b)));
    }
    for(int i = 1; i <= N; ++i) daddy[i] = i;
}
int nrm,total;
void kruskal()
{
    int a,b,c;
    while(!Q.empty())
    {
        c = Q.top().first;
        a = Q.top().second.first;
        b = Q.top().second.second;
        Q.pop();
        if(whos_ur_daddy(a) != whos_ur_daddy(b))
        {
            couple(a,b);
            total += c;
            ++nrm;
            sol.push_back(make_pair(a,b));
        }
    }
}

void print()
{
    printf("%d\n%d\n",total,nrm);
    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();
    kruskal();
    print();

    return 0;
}