#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#define INF 0x3f3f3f3f

using namespace std;
vector <pair<int,int>>g[50003];
bool cn;
bitset <50003> viz;
queue <int> q;
int n,m,a,b,c;
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d", &n,&m);
    for(int i=0;i<m;++i)
    {
        scanf("\n%d %d %d", &a,&b,&c);
        g[a].push_back({b,c});
    }
    vector<int> d(n+1,INF), noade(n+1,0);
    q.push(1), d[1]=0;
    while(!q.empty() && !cn)
    {
        a=q.front();
        q.pop();
        viz[a]=0;
        for(auto i:g[a])
        {
            b=i.first, c=i.second;
            if(d[b]>d[a]+c)
            {
                d[b]=d[a]+c;
                if(noade[b]>n)
                    cn=1;
                else
                {
                    q.push(b);
                    viz[b]=1;
                    ++noade[b];
                }
            }
        }
    }
    if(!cn)
        for(int i=2;i<=n;++i)
            cout<<d[i]<<" ";
    else
        cout<<"Ciclu negativ!\n";
    return 0;
}