#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

#define NMAX 50007
#define S second
#define F first

vector < pair < int , int > > G[NMAX];
queue < int > Q;
vector < pair < int , int > > :: iterator u;
int X,Y,cost,N,M,node,i;
bool marked[NMAX];
int D[NMAX],w[NMAX];

int main()
{
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);

for (scanf("%d%d",&N,&M);M;--M)
{
    scanf("%d%d%d",&X,&Y,&cost);
    G[X].push_back(make_pair(Y,cost));
}

Q.push(1);
fill(D+2,D+N+1,INT_MAX);

while (!Q.empty())
{
    node=Q.front();

    for (u=G[node].begin();u!=G[node].end();++u)
    if (D[node]+(*u).S<=D[(*u).F])
    {
        if (w[(*u).F]==N)
        {
            printf("Ciclu negativ\n");
            return 0;
        }

        ++w[(*u).F];
        D[(*u).F]=D[node]+(*u).S;

        if (!marked[(*u).F])
        {
            marked[(*u).F]=true;
            Q.push((*u).F);
        }
    }

    Q.pop();
    marked[node]=false;
}

for (i=2;i<=N;++i)
printf("%d ",D[i]);

return 0;
}