#include <iostream>
#include <fstream>

using namespace std;

const int INF = 1000000;

int main() {
    ifstream f("dijkstra.in");
    ofstream 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 count = 1; count <= n; count++) {
        int u = -1;
        int minDist = INF;

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

        // 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;
}