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

#define NMAX 200005
#define MMAX 500005

using namespace std;

struct nod
{
    int val;
    int rang = 1;
    nod *urm = this;
}*nodes[NMAX];

nod* get_top(nod *&a)
{
    if(a->urm != a)
        return get_top(a->urm);
    return a->urm;
}

void merge_sets(nod *&a, nod *&b)
{
    nod *x = get_top(a);
    nod *y = get_top(b);
    if(x->rang > y->rang)
        y->urm = x;
    else if(x->rang < y->rang)
        x->urm = y;
    else
    {
        y->urm = x;
        x->rang++;
    }

}

int N,M;
vector<pair<int, pair<int,int> > > graf;

void citire()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        graf.push_back(make_pair(c,make_pair(x,y)));
    }
    for(int i=1;i<=N;i++)
        nodes[i]=new nod;
}

int suma;
vector<pair<int,int> > rez;
void kruskal()
{
    sort(graf.begin(),graf.end());
    for(vector<pair<int,pair<int,int> > >::iterator ii = graf.begin();ii!=graf.end();ii++)
    {
        int nod1 = ii->second.first;
        int nod2 = ii->second.second;
        int cost = ii->first;

        if(get_top(nodes[nod1])!=get_top(nodes[nod2]))
        {
            merge_sets(nodes[nod1],nodes[nod2]);
            suma+=cost;
            rez.push_back(make_pair(nod1,nod2));
        }

    }
}

void afisare()
{
    printf("%d\n%d\n",suma,rez.size());
    for(vector<pair<int,int> >::iterator ii=rez.begin();ii!=rez.end();ii++)
        printf("%d %d\n",ii->first,ii->second);
}


int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    kruskal();
    afisare();
    return 0;
}