#include <iostream>
#include <fstream>
#define inf 1000000000
using namespace std;
long cost[50000], n, m, i, j;
struct muchii
{
    int a,b,c;
};
muchii x[250001];
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>x[i].a>>x[i].b>>x[i].c;
    cost[1]=0;
    for(i=2;i<=n;++i)
        cost[i]=inf;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(cost[x[i].a]+x[i].c<cost[x[i].b])
                cost[x[i].b]=cost[x[i].a]+x[i].c;
    for(i=1;i<=m;i++)
        {
            if(cost[x[i].a]+x[i].c<cost[x[i].b])
                printf("Ciclu negativ!");
                break;
                return 0;
        }
    for (i=2; i<=n; i++)
        fout<<cost[i]<<' ';
    return 0;

}