#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include <unordered_map>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int LMAX = 14;
vector<pair<int, int>> L[LMAX];
bool inTree[LMAX];
vector<pair<int, int>> edges;


int main() {
    int n, m, x, y, c, sum;
    fin>>n>>m;
    while (m--) {
        fin>>x>>y>>c;
        x--;
        y--;
        L[x].push_back({y, c});
        L[y].push_back({x, c});
    }
    vector<int> dist(n+1, INT_MAX);
    inTree[0] = 1;
    dist[0] = 0;
    sum = 0;
    for (pair<int, int> vec : L[0]) {
        dist[vec.first] = vec.second;
    }
    for (int i = 0; i < n; i++) {
        int mini = INT_MAX, u;
        u = 0; //nodul care conecteaza cea mai ok muchie
        for (int j = 0; j < n; j++) {
            if (!inTree[j] && dist[j] < mini) {
                mini = dist[j];
                u = j;
            }
        }
        for (pair<int, int> vec : L[u]) {
            if (inTree[vec.first] && vec.second == mini) {
                inTree[u] = 1;
                sum+=mini;
                edges.push_back({vec.first, u});
                for (pair<int, int> x : L[u]) {
                    dist[x.first] = min(dist[x.first], x.second);
                }
                break;
            }
        }
    }
    fout<<sum<<endl<<edges.size()<<endl;
    for (auto vec : edges) {
        fout<<vec.first + 1<<" "<<vec.second + 1<<endl;
    }




    fin.close();
    fout.close();
    return 0;
}