#include <cstdio>
#include <queue>
#define MAXN 50000
#define MAXM 250000

using namespace std;

queue <int> q;

const int INF = 0x3f3f3f3f;

int n, m, r, lista[MAXN+1], nxt[MAXM+1], val[MAXM+1], d[MAXM+1], dist[MAXN+1], nrq[MAXN+1];
bool ok[MAXN+1];

inline void adauga(int x, int y, int z)
{
    val[++r]=y;
    nxt[r]=lista[x];
    lista[x]=r;
    d[r]=z;
}

bool bellman_ford()
{
    int p, vecin, nod;

    q.push(1);
    nrq[1]++;
    ok[1]=1;

    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        ok[nod]=0;

        p=lista[nod];

        while(p)
        {
            vecin=val[p];
            if(dist[nod] + d[p] < dist[vecin])
            {
                dist[vecin]=dist[nod] + d[p];
                if(!ok[vecin])
                {
                    if(nrq[vecin] > n)
                        return 0;
                    q.push(vecin);
                    nrq[vecin]++;
                }

            }

            p=nxt[p];
        }
    }

    return 1;
}

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

    int i, x, y, z;

    scanf("%d%d", &n, &m);

    for(i=0;i<m;++i)
    {
        scanf("%d%d%d", &x, &y, &z);
        adauga(x, y, z);
    }

    for(i=2;i<=n;++i)
        dist[i]=INF;

    if(bellman_ford())
        for(i=2;i<=n;++i)
            printf("%d ", dist[i]);

    else printf("Ciclu negativ!");

    return 0;
}