#include "ReadWriter.h"
#include "climits"
//string, fstream, iostream, vector, Edge.h - included in ReadWriter.h

//Можно создавать любые классы и методы для решения задачи

using namespace std;

//method for finding vertex with minimal distance
int findNext(int N, bool *visited, const int *distance) {

    int i = 0, minimum = INT_MAX;

    for (int j = 0; j < N; j++)
        if (!visited[j] && distance[j] <= minimum) {
            minimum = distance[j];
            i = j;
        }
    visited[i] = true;
    return i;
}

//Основной метод решения задачи, параметры:
//N - количество вершин, M - количество ребер в графе
//edges - вектор ориентированных ребер, каждое ребро представлено 3-мя числами (А, В, W),
// где A и B - номера вершин, которые оно соединяет (Путь строго из А в В), и W - вес ребра
//передается по ссылке (&), чтобы не копировать, изменять вектор и его значения можно.
//Результат также в виде вектора кратчайших расстояний из 0-й вершины во все остальные начиная с 1-й, то есть N-1 значение должно быть
void solve(int N, int M, vector<Edge> &edges, vector<int> &result) {

    int **graph = new int *[N];
    bool *visited = new bool[N];
    int *distance = new int[N];

    for (int i = 0; i < N; i++) {
        graph[i] = new int[N];

        for (int j = 0; j < N; j++)
            graph[i][j] = 0;

        visited[i] = false;
        distance[i] = INT_MAX;
    }

    //setting weight for each point
    for (int i = 0; i < edges.size(); i++) {
        graph[edges[i].A][edges[i].B] = edges[i].W;
    }

    //Dijkstra algorithm
    int count = 1;
    distance[0] = 0;

    while (count++ < N) {

        int curV = findNext(N, visited, distance);

        for (int newV = 0; newV < N; ++newV)
            if (!visited[newV] && graph[curV][newV] != 0 && distance[curV] != INT_MAX) {
                int path = distance[curV] + graph[curV][newV];
                if (path < distance[newV])
                    distance[newV] = path;
            }
    }

    for (int i = 1; i < N; ++i) {
        result.push_back(distance[i]);
    }

    delete[] distance;
    delete[] visited;
    for (int i = 0; i < N; i++)
        delete[] graph[i];
    delete[] graph;


}

int main() {
    ReadWriter rw;
    //Входные параметры
    //N - количество вершин, M - количество ребер в графе
    int N, M;
    rw.read2Ints(N, M);

    //Вектор ребер, каждое ребро представлено 3-мя числами (А, В, W), где A и B - номера вершин, которые оно соединяет, и W - вес ребра
    //Основной структурой выбран вектор, так как из него проще добавлять и удалять элементы (а такие операции могут понадобиться).
    vector<Edge> edges;
    rw.readEgdes(M, edges);

    //Основной структурой для ответа выбран вектор, так как в него проще добавлять новые элементы.
    vector<int> result;

    //Алгоритм решения задачи
    solve(N, M, edges, result);

    //Выводим результаты
    rw.writeInt(result.size());
    rw.writeIntValues(result);

    return 0;
}