#include<cstdio>
#include<vector>
#include<utility>
#include<iterator>
#include<algorithm>
#include<deque>
#include<bitset>
#define NMAX 50000+5
#define MMAX 250000+5
#define oo 1<<30
using namespace std;
vector<pair<int,int> > V[NMAX];
vector<pair<int,int> >::iterator it;
int N,M,x,y,c,i,j,p;
int costs[NMAX];
int cnt[NMAX];
bitset<NMAX> mark;
deque<int> Dq;
int bf()
{
    Dq.push_back(1);
    mark[1]=1;
    for(;!Dq.empty();)
    {
        p=Dq.front();
        Dq.pop_front();
        mark[p]=0;
        for(it=V[p].begin();it!=V[p].end();it++)
        {
            if(!mark[it->first] && costs[p]+it->second < costs[it->first])
            {
                costs[it->first]=costs[p]+it->second;
                mark[it->first]=1;
                Dq.push_back(it->first);
            }
        }
        cnt[p]++;
        if(cnt[p]==N) return 0;
    }
    return 1;
}
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));
    }
    for(i=2; i<=N; i++) costs[i]=oo;
    if(bf()==0) printf("Ciclu negativ!\n");
    else for(i=2; i<=N; i++) printf("%d ",costs[i]);
    return 0;
}