// O(n^2)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#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 && cost[u][i] != 0x3f3f3f3f && 
                !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));
    minCostEdge[1] = 0;

    int sol = 0;
    vector<pair<int, int> > solution;
    for (i = 1; i <= n; ++i) {
        u = findMinNode();
        if (parent[u]) {
            solution.push_back(make_pair(u, parent[u]));
            sol += cost[u][parent[u]];
        }
        inMST[u] = true;
        updateEdges(u);
    }

    printf ("%d\n", sol);
    printf ("%d\n", n - 1);
    for (i = 0; i < solution.size(); ++i)
        printf ("%d %d\n", solution[i].first, solution[i].second);
}


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