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

#define NMAX 200005

using namespace std;

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

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

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

void merge_sets(nod *a, nod *b)
{
    nod *A = get_top(a);
    nod *B = get_top(b);

    if(A->rang > B->rang)
        B->urm = A;
    if(B->rang > A->rang)
        A->urm = B;
    if(B->rang == A->rang)
    {
        B->urm = A;
        A->rang++;
    }
}

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;
}

vector<pair<int,int> > rez;
int cost_total;
void kruskal()
{
    sort(graf.begin(),graf.end());
    for(vector<pair<int,pair<int,int> > >::iterator ii = graf.begin();ii!=graf.end();ii++)
    {
        int a = ii->second.first;
        int b = ii->second.second;
        if(get_top(nodes[a]) != get_top(nodes[b]))
        {
            cost_total += ii->first;
            merge_sets(nodes[a],nodes[b]);
            rez.push_back(make_pair(a,b));
        }
    }
}

void afisare()
{
    printf("%d\n%d\n",cost_total,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;
}