#include <stdio.h>
#include <queue>
#define NMAX 50001
# define INF 0x3f3f3f3f
using namespace std;

struct nod{
    int inf,cost;
    nod *urm;
};
nod *g[NMAX];
int n,m,v[NMAX],cnt[NMAX],q=0;
queue < int > Q;
bool viz[NMAX];
void add(int x,int y,int z)
{
    nod *aux=new nod;
    aux->inf=y;
    aux->cost=z;
    aux->urm=g[x];
    g[x]=aux;
}

void citire()
{
    freopen ("bellmanford.in","r",stdin);
    scanf ("%d%d",&n,&m);
    int x,y,z;
    for (int i=1;i<=m;i++)
    {
        scanf ("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    v[1]=0;
    memset(v,INF,sizeof(v));
    v[1]=0;
    Q.push(1);
    int s,nd;
    viz[1]=true;
    while (!Q.empty())
    {
        nd=Q.front();
        Q.pop();
        viz[nd]=false;
        for (nod *p=g[nd];p;p=p->urm)
        {
            s=v[nd]+p->cost;
            if (s<v[p->inf])
            {
                v[p->inf]=s;
                if (!viz[p->inf])
                {
                    if (cnt[p->inf]>n)
                        q=1;
                    else
                    {
                    cnt[p->inf]++;
                    Q.push(p->inf);
                    viz[p->inf]=true;
                    }
                }
            }
        }
    }
}




void afis()
{
    freopen ("bellmanford.out","w",stdout);
    if (q)
        printf("Ciclu negativ!");
    else

        for (int i=2;i<=n;i++)
        {
            if (v[i]<INF)
                printf("%d ",v[i]);
            else
                printf("0 ");
        }
}

int main()
{
    citire();
    afis();
    return 0;
}