#include <iostream>
#include <fstream>

using namespace std;

const int INF = 1000000;

int main() {
    ifstream f("dijkstra.in");
    ifstream of("dijkstra.out");
    int n, m;
    f >> n >> m;
    int a[n + 1][n + 1];
    int src = 1;
    int x, y, c;

    // Initialize the adjacency matrix with INF
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = INF;
        }
    }

    // Read the edges and their weights
    for (int i = 1; i <= m; i++) {
        f >> x >> y >> c;
        a[x][y] = c;
    }

    int d[n + 1];
    bool visited[n + 1];

    // Initialize distances and visited array
    for (int i = 1; i <= n; i++) {
        d[i] = INF;
        visited[i] = false;
    }

    d[src] = 0;

    for (int i = 1; i <= n; i++) {
        int u = -1;
        int minDist = INF;

        // Find the unvisited vertex with the minimum distance
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && d[j] < minDist) {
                u = j;
                minDist = d[j];
            }
        }

        // If no unvisited vertex is found, break the loop
        if (u == -1) {
            break;
        }

        // Mark the vertex as visited
        visited[u] = true;

        // Update the distances of the neighboring vertices
        for (int v = 1; v <= n; v++) {
            if (!visited[v] && a[u][v] != INF && d[u] + a[u][v] < d[v]) {
                d[v] = d[u] + a[u][v];
            }
        }
    }

    // Print the distances
    for (int i = 1; i <= n; i++) {
        of << d[i] << " ";
    }

    return 0;
}