#include <cstdio>
#include<vector>
#include<queue>
#include<bitset>
#include<cmath>
#define NMAX 50001
#define INF 5000001
using namespace std;
struct graf
{
    int l,r;
};
vector<graf>v[NMAX];
queue<int>q;
bitset<NMAX>viz(false);
int x,y,c,n,m,i;
int dist[NMAX],nr[NMAX];
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;++i) dist[i]=INF;
    for (i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        graf X;
        X.l=y;X.r=c;
        v[x].push_back(X);
    }
    dist[1]=0;viz[1]=1;q.push(1);
    bool e=false;
    while(!q.empty() && !e)
    {
        int x=q.front();
        q.pop();
        viz[x]=1;
        vector<graf>::iterator it;
        for (it=v[x].begin();it!=v[x].end();++it)
        {
            graf X=*it;
            if (dist[x]<INF)
            {
                if (dist[X.l]>dist[x]+X.r)
                {
                    dist[X.l]=dist[x]+X.r;
                    if (!viz[X.l])
                    {
                        if (nr[X.l]>n) e=true;
                            else
                            {
                                q.push(X.l);
                                viz[X.l]=true;
                                ++nr[X.l];
                            }
                    }
                }
            }
        }
    }
    if (e!=0)
    {
        for (i=2;i<=n;++i) printf("%d ",dist[i]);
    }
    else printf("Ciclu negativ!\n");
    return 0;
}