#include <iostream>

using namespace std;

int const maxn = 100000;
int const inf = 1000000;

struct graf{
    int vc, cost;
    graf *next;
} *L[50001];

int n,m,d[50001];

void addx(graf *&prim, int vc, int c)
{
    graf *q = new graf;
    q -> vc=  vc;
    q->cost = c;
    q->next = prim;
    prim = q;
}

void citire()
{
    freopen("bellmanford.in", "r", stdin);
    scanf("%d%d", &n, &m);

    d[1]= 0;
    for(int i=2;i<=n;i++)
        d[i] = inf;

    for(int i=1;i<=m;i++)
    {
        int x,y,c;

        scanf("%d%d%d", &x, &y, &c);

        addx(L[x], y, c);

        if(x == 1)
            d[y] = c;

    }
    for(int i=1;i<=n;i++)
        cout<<d[i]<<" ";

}

void bellman()
{
    for(int k=1;k<=n;k++)
        for(graf *p = L[k]; p; p = p->next)
            if(d[p->vc]> d[k] + p->cost)
                d[p->vc] = d[k] + p->cost;

}

int ciclu()
{
    for(int k=1;k<=n;k++)
        for(graf *p = L[k]; p; p = p->next)
            if(d[p->vc]> d[k] + p->cost)
                return 0;
    return 1;
}
int main()
{
    citire();

    bellman();
    freopen("bellmanford.out","w",stdout);
    if(ciclu() == 1)
        for(int i =2;i<=n;i++)
            printf("%d ",d[i]);
    else
        printf("Ciclu negativ!");
    return 0;
}