#include <fstream>

using namespace std;
int a[3][250005], start[50005], cost[50005], c[50005], n, m;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
void init()
{
    for (int i = 1; i <= n; i++)
        cost[i] = 50000001;
}
void ford(int nod);
int main()
{
    int i, x, y;
    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> x >> y >> a[2][i];
        a[0][i] = y;
        a[1][i] = start[x];
        start[x] = i;
    }
    init(); //initializez costurile cu valoarea maxima posibila
    cost[1] = 0;
    ford(1);
    for (i = 2; i <= n; i++) {
        if (cost[i] == 50000001)
            cout << 0 << " ";
        else
            cout << cost[i] << " ";
    }
    return 0;
}
void ford(int nod)
{
    int ps = 1, pi = 1, x, viz[50005] = {0};
    c[1] = nod;
    viz[nod] = 1;
    while (ps <= pi) {
        x = start[c[ps]];
        viz[c[ps]] = 0;
        while (x) {
            if (cost[c[ps]] + a[2][x] < cost[a[0][x]]) {
                cost[a[0][x]] = cost[c[ps]] + a[2][x];
                if (viz[a[0][x]] == 0) {
                    c[++pi] = a[0][x];
                    viz[a[0][x]] = 1;
                }
            }
            x = a[1][x];
        }
        ps++;
    }
}