#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#define NMAX 50007
#define inf 1000000007
FILE *fin, *fout;
using namespace std;
struct muchie
{
    int nod;
    int cost;
} tmp;
vector<muchie> adj[NMAX];
queue<int> q;
int n, x, m, ans[NMAX], cnt[NMAX], node, sze, sol;
void citire()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; ++i)
    {
        scanf("%d %d %d", &x, &tmp.nod, &tmp.cost);
        adj[x].push_back(tmp);
    }
}
int bellmanford()
{
    memset(ans, inf, sizeof(ans));
    ans[1] = 0;
    q.push(1);
    cnt[1] = 1;
    while(!q.empty())
    {
        node = q.front();
        q.pop();
        sze = adj[node].size();
        for(int i = 0; i< sze; ++i)
        {
            if(ans[node] + adj[node][i].cost < ans[adj[node][i].nod])
            {
                ans[adj[node][i].nod] = ans[node] + adj[node][i].cost;
                q.push(adj[node][i].nod);
                cnt[adj[node][i].nod] ++;
                if(cnt[adj[node][i].nod] > n) return 1;
            }
        }
    }
    return 0;
}
void afisare()
{
    if(sol == 1) printf("Ciclu negativ!\n");
    else
    {
        for(int i = 2; i<= n; ++i) printf("%d ", ans[i]);
        printf("\n");
    }
}
int main()
{
    fin = freopen("bellmanford.in", "r", stdin);
    fout = freopen("bellmanford.out", "w", stdout);
    citire();
    sol = bellmanford();
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}