#include <fstream>

#define NMAX 505
#define INF 100000005

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, x0;
int x, y, c;
int cost[NMAX][NMAX];
int dmin[NMAX], pre[NMAX];
int i, j;

int bellmanford();

int main()
{
    ///CITIRE
    fin >>n>>m; x0 = 1;

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

    for (i = 1; i <= m; ++i)
    {
        fin >>x>>y>>c;
        cost[x][y] = c;
    }

    ///AFISARE
    if (!bellmanford()) fout <<"Ciclu negativ!";
    else
        for (i = 2; i <= n; ++i)
            fout <<dmin[i]<<' ';

    fout <<'\n';
    fout.close();
    return 0;
}

int bellmanford()
{
    int k, x, y;
    for (i = 1; i <= n; ++i)
        dmin[i] = INF, pre[i] = x0;
    dmin[x0] = pre[x0] = 0;

    for (k = 1; k <= n; ++k)
        for (x = 1; x <= n; ++x)
            for (y = 1; y <= n; ++y)
                if (cost[x][y] != INF && dmin[x] + cost[x][y] < dmin[y])
                    dmin[y] = dmin[x] + cost[x][y];

    for (x = 1; x <= n; ++x)
        for (y = 1; y <= n; ++y)
            if (cost[x][y] != INF && dmin[x] + cost[x][y] < dmin[y])
                return 0;

    return 1;
}