// O(n^2)
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 801

using namespace std;
int cost[N][N];
int parent[N];
bool inMST[N];
int n, m;

int minCostEdge[N];

void updateEdges(int u) {
    for (int i = 1; i <= n; ++i)
        if (u != i && !inMST[i] &&
                minCostEdge[i] > cost[u][i]) {
            minCostEdge[i] = cost[u][i];
            parent[i] = u;
        }
}

int findMinNode() {
    int minim = 0x3f3f3f3f;
    int u = 0;
    for (int i = 1; i <= n; ++i)
        if (!inMST[i] && minim > minCostEdge[i])
            minim = minCostEdge[i],
            u = i;
    return u;
}
void prim() {
    
    int i, j, u;
    memset (minCostEdge, 0x3f3f3f3f, sizeof(minCostEdge));

    inMST[1] = true;
    updateEdges(1);
    for (i = 1; i < n; ++i) {
        u = findMinNode();
        inMST[u] = true;
        updateEdges(u);
    }

    int sol = 0;
    for (i = 1; i <= n; ++i)
        if (parent[i])
            sol += cost[i][parent[i]];

    printf ("%d\n", sol);
    printf ("%d\n", n - 1);
    for (i = 1; i <= n; ++i)
        if (parent[i])
            printf ("%d %d\n", i, parent[i]);
}


int main() {
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout); 
    memset (cost, 0x3f3f3f3f, sizeof(cost));

    int p, q, c;
    scanf ("%d %d", &n, &m);
    while (m--) {
        scanf ("%d %d %d", &p, &q, &c);
        cost[p][q] = c;
        cost[q][p] = c;
    }

    prim();
}