#include <iostream>
#include <fstream>
#include <limits.h>

using namespace std;

ifstream be("apm.in");
ofstream ki("apm.out");

#define INF 999999

struct edge {
    int from;
    int to;
    int weight;
};

void read(int& n, int& m, int wMatr[][101]) {
    be >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            wMatr[i][j] = INF;
        }
    }

    for (int i = 1; i <= m; i++) {
        int from, to, weight;
        be >> from >> to >> weight;
        wMatr[from][to] = weight;
    }
}

void prim(int n, int m, int wMatr[][101], edge* mTree, int& mF, int start) {
    bool bMatr[101][101] = { 0 };
    int visited[101] = { 0 };
    int vis = 1;
    visited[start] = 1;

    int wSum = 0;

    while (vis < n) {
        int minimum = INT_MAX;
        int min_index_from, min_index_to;
        for (int i = 1; i <= n; i++) {
            if (visited[i] == true) {
                for (int j = 1; j <= n; j++) {
                    if (wMatr[i][j] != INF && visited[j] == false && wMatr[i][j] < minimum && bMatr[i][j] == 0) {
                        minimum = wMatr[i][j];
                        min_index_from = i;
                        min_index_to = j;
                    }
                }
            }
        }
        bMatr[min_index_from][min_index_to] = 1;
        visited[min_index_to] = 1;
        vis++;
        mF++;
        mTree[mF].from = min_index_from;
        mTree[mF].to = min_index_to;
        mTree[mF].weight = minimum;
        wSum += minimum;
    }

    cout << wSum << endl;
    cout << mF << endl;
    for (int i = 1; i <= mF; i++) {
        cout << mTree[i].from << " " << mTree[i].to << " " << mTree[i].weight << endl;
    }

}

int main()
{
    int n, m;
    int wMatr[101][101];
    int mF = 0;
    edge mTree[201];
    read(n, m, wMatr);
    prim(n, m, wMatr, mTree, mF, 1);
}