#include<cstdio>
#include<deque>
#include<utility>
#include<vector>
#define N 50010
using namespace std;
int n,m,x,y,c,q[N],C[N],cnt[N];
vector<pair<int, int> > v[N] ;
deque<int> Q;
void bellman();
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
    }
    bellman();
    return 0;
}
void bellman()
{
    int oo=100000000,i;
    vector<pair<int,int> >::iterator it;
    for(i=1;i<=n;i++)
    C[i]=oo;
    C[1]=0;
    Q.push_back(1);
    q[1]=1;
    for(;Q.size();)
    {
        i=Q.front();Q.pop_front();
        q[i]=0;
        for(it=v[i].begin();it!=v[i].end();it++)
        {
            if(C[it->first]<=C[i]+it->second) continue;
            C[it->first]=C[i]+it->second;
            cnt[it->first]++;
            if(cnt[it->first]>=n)
            {
                printf("Ciclu negativ!\n");
                return ;
            }
            if(!q[it->first])
               {
                   Q.push_back(it->first);
                   q[it->first]=1;
               }

        }

    }
    for(i=2;i<=n;i++) printf("%d ",C[i]);
}