#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;
}