#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
#define INF 1000000000
#define MAXN 50001
using namespace std;
vector <pair <int,int> >v[MAXN];
int dist[MAXN],ap[MAXN];
queue <int> q;
bool incoada[MAXN],ciclu;
int main()
{
    FILE *fin,*fout;
    fin=fopen("bellmanford.in","r");
    fout=fopen("bellmanford.out","w");
    int n,m,x,y,cost;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        fscanf(fin,"%d%d%d",&x,&y,&cost);
        v[x].push_back(make_pair(y,cost));
    }
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    q.push(1);dist[1]=0;ap[1]=1;
    while(!q.empty() && !ciclu)
    {
        x=q.front();q.pop();incoada[x]=false;
        for(unsigned int i=0;i<v[x].size();i++)
        {
            y=v[x][i].first;cost=v[x][i].second;
            if(dist[y]>dist[x]+cost)
            {
                dist[y]=dist[x]+cost;
                if(ap[y]==n-1)
                    ciclu=true;
                else
                {
                    ap[y]++;
                    if(!incoada[y])
                        q.push(y),incoada[y]=true;
                }
            }
        }
    }
    if(ciclu)
        fprintf(fout,"Ciclu negativ!");
    else
        for(int i=2;i<=n;i++)
            fprintf(fout,"%d ",dist[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}