#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<pair<int, int>>> v(101);
vector<int> selected;
bool vis[101];
int t[101];

int main() {
    ifstream cin("prim.in");
    ofstream cout("prim.out");
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int c, x, y;
        cin >> x >> y >> c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    selected.push_back(1);
    vis[1] = true;
    int edges = 0, sum = 0;
    while (edges < n - 1) {
        int minCost = INT_MAX, minX, minY;
        for (int i = 0; i < selected.size(); ++i) {
            for (int j = 0; j < v[selected[i]].size(); ++j) {
                if (!vis[v[selected[i]][j].first] && v[selected[i]][j].second < minCost) {
                    minCost = v[selected[i]][j].second;
                    minX = selected[i];
                    minY = v[selected[i]][j].first;
                }
            }
        }
        t[minY] = minX;
        sum += minCost;
        vis[minY] = true;
        selected.push_back(minY);
        ++edges;
    }
    cout << sum << "\n";
    for (int i = 1; i <= n; ++i) {
        cout << t[i] << " ";
    }
}