#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct edge{
    int node1;
    int node2;
    short value;
} EDGE;

typedef struct node{
    int nodeIndex;
    int setRank;
    struct node *parent;
} NODE;

int n,m;

vector<EDGE> edges;
EDGE addedEdges[200000];
NODE *sets[200001];

bool cmp(const EDGE &e1, const EDGE &e2){
    if (e1.value < e2.value){
        return true;
    } else {
        return false;
    }
}

void initSets(){
    for (int i=1; i<=n; i++){
        NODE *n = (NODE*) malloc(sizeof(NODE));
        n->nodeIndex = i;
        n->parent = n;
        n->setRank = 0;
        sets[i] = n;
    }
}

NODE *findSet(NODE *p){
    if (p->nodeIndex == p->parent->nodeIndex){
        return p;
    } else {
        p->parent = findSet(p->parent);
        return p->parent;
    }
}

void unionSet(NODE *s1, NODE *s2){
    if (s2->setRank > s1->setRank){
        s1->parent = s2;
    }
    else if (s2->setRank < s1->setRank){
        s2->parent = s1;
    } else {
        s1->parent = s2;
        s2->setRank = s2->setRank+1;
    }
}

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

    //read data
    scanf("%d %d", &n, &m);

    int node1, node2, value;
    for (int i=0; i<m; i++){
        scanf("%d %d %d", &node1, &node2, &value);
        EDGE e;
        e.node1 = node1;
        e.node2 = node2;
        e.value = value;

        edges.push_back(e);
    }

    sort(edges.begin(), edges.end(), cmp);

    initSets();

    //solve problem
    int addedEdgesNr = 0;

    long long solutionSum = 0;

    for (int i=0; i<edges.size(); i++){
        if (addedEdgesNr == n-1){
            break;
        }

        EDGE currentEdge = edges[i];

        NODE *set1Repr = findSet(sets[currentEdge.node1]);
        NODE *set2Repr = findSet(sets[currentEdge.node2]);

        if (set1Repr->nodeIndex != set2Repr->nodeIndex){
            unionSet(set1Repr, set2Repr);
            addedEdges[addedEdgesNr++] = currentEdge;
            solutionSum += currentEdge.value;
        }
    }

    //output results
    printf("%lld\n", solutionSum);
    printf("%d\n", n-1);

    for (int i=0; i<addedEdgesNr; i++){
        printf("%d %d\n", addedEdges[i].node1, addedEdges[i].node2);
    }

    return 0;
}