#include <fstream>
#include <climits>
#define InFile  "bellmanford.in"
#define OutFile "bellmanford.out"
#define maxn  50010
#define maxm 250010

using namespace std;

struct muchie
{
    long int a, b, c;
} e[maxm];

long int n, m, i, j, k, cost[maxn];

void init ()
{
    long int i;
    cost[1] = 0;
    for(i=2; i<=n; i++)
        cost[i] = INT_MAX;
}

void solve ()
{
    long int i, j;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            if (cost[e[j].a] + e[j].c < cost[e[j].b])
                cost[e[j].b] = cost[e[j].a] + e[j].c;
}

long check_negativ ()
{
    long int i;
    for (i=1; i<=m; i++)
        if (cost[e[i].a] + e[i].c < cost[e[i].b])
            return 1;
    return 0;
}

int main ()
{
    ifstream fin (InFile);
    fin >> n >> m;
    for (i=1; i<=m; i++)
        fin >> e[i].a >> e[i].b >> e[i].c;
    fin.close();

    init ();
    solve ();

    ofstream fout (OutFile);
    if (check_negativ())
    {
        fout << "Ciclu negativ!\n";
        return 0;
    }
    for (i=2; i<=n; i++)
        fout << cost[i] << ' ';
    fout.close();
    return 0;
}