#include <iostream>
#include <queue>
#include <fstream>
#include <vector>

using namespace std;

#define MAX_N 50005

const int INF = 1005;

struct muchie
{
    int c, x, y;
};

int d[MAX_N];

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    vector<muchie> muchii;
    int n, m, x, y, c, i;
    bool ok = false;

    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        muchii.push_back({c, x, y});
    }

    for (i = 1; i <= n; i++)
        d[i] = INF;

    d[1] = 0;
    do
    {
        ok = false;

        for (muchie m : muchii)
        {
            int x = m.x;
            int y = m.y;
            int cost = m.c;

            if (d[x] < INF && d[y] > d[x] + cost)
            {
                d[y] = d[x] + cost;
                ok = true;
            }
        }

    } while (ok);

    for (i = 2; i <= n; i++)
    {
        if (d[i] != INF)
            g << d[i] << ' ';
        else
            g << 0 << ' ';
    }
    return 0;
}