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

using namespace std;
const int Nmax = 200005;

struct cmp{
    bool operator()(const pair<int,pair<int,int> > A, const pair<int,pair<int,int> > B)const
    {
        return A.second.second > B.second.second;
    }
};

priority_queue< pair<int,pair<int,int> > , vector< pair<int,pair<int,int> > > , cmp> Q;
vector <pair<int,int> > answer;

int daddy[ Nmax ],N,M,cost;

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(a,make_pair(b,c)));
    }
    for(int i = 1; i <= N; ++i)
        daddy[ i ] = i;
}

int whos_ur_daddy(int nodc)
{
    if(daddy[ nodc ] != nodc)
        daddy[ nodc ] = whos_ur_daddy(daddy[ nodc ]);
    return daddy[ nodc ];
}

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

void kruskal()
{
    int i=0,a,b,cst;
    while(i!=N-1)
    {
        a = Q.top().first;
        b = Q.top().second.first;
        cst = Q.top().second.second;
        Q.pop();
        if(whos_ur_daddy(a) != whos_ur_daddy(b))
        {
            ++i;
            cost += cst;
            couple(whos_ur_daddy(a),whos_ur_daddy(b));
            answer.push_back(make_pair(a,b));
        }
    }
}

void print()
{
    printf("%d\n%d\n",cost,answer.size());
    for(int i=0;i<answer.size();++i)
        printf("%d %d\n",answer[i].first,answer[i].second);
}

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

    read();
    kruskal();
    print();

    return 0;
}