#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
vector <pair <int,int> > a[50010];
queue <int> q;
int x, y, n, m, z;
int d[50010], nr[50010];
bool marcat[100010];
bool bfs(int nod)
{
    d[nod]=0;
    q.push(nod);
    marcat[nod] = true;
    while(!q.empty())
    {
        int vf=q.front();
        q.pop();

        for(int i=0; i<a[vf].size(); i++)
        {
            if(d[a[vf][i].first]>d[vf]+a[vf][i].second)
            {
                if(marcat[a[vf][i].first]==false)
                    {
                        q.push(a[vf][i].first);
                        marcat[a[vf][i].first]=true;
                    }
                d[a[vf][i].first]=d[vf]+a[vf][i].second;
                nr[a[vf][i].first]++;
            }
            if(nr[a[vf][i].first]>=n)
                return true;
        }     marcat[vf]=false;
    }
    return false;
}
int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(make_pair(y,z));
    }
    for(int i=1; i<=n; i++)
        d[i]=2000000000;
    if(bfs(1)==true) printf("Ciclu negativ!");
    else
    {
        for(int i=2; i<=n; i++)
            printf("%d ", d[i]);
    }
    return 0;
}