#include <cstdio>
#include <vector>
#include <queue>
#define LMAX 50005
#define INF 999999999

using namespace std;
FILE *fin=fopen("bellmanford.in","r");
FILE *fout=fopen("bellmanford.out","w");

struct nod{
    int v;
    int c;
};
vector<nod>V[LMAX];

queue<int>Q;

int fol[LMAX];//de cate ori am folosit nodul pentru imbunatatirea drumului
int cmin[LMAX];//drumul minim pana la fiecare nod

int n, m;
int startn, endn, c;
nod safie;
bool negativ;
int xx;
int main()
{
    fscanf(fin,"%d %d",&n,&m);
    for (int i=1;i<=m;i++)
        {
         fscanf(fin,"%d %d %d",&startn,&endn,&c);
         safie.c=c;
         safie.v=endn;
         V[startn].push_back(safie);
        }
    //trebuie sa initializez distantele minime cu INF pentru fiecare nod in afara de cel din care pornesc
    for (int i=2;i<=n;i++)
        cmin[i]=INF;
    Q.push(1);
    while (!Q.empty())
        {
         xx=Q.front();
         Q.pop();
         for (int i=0;i<V[xx].size();i++)
            if (cmin[V[xx][i].v]>cmin[xx]+V[xx][i].c)
                {
                 cmin[V[xx][i].v]=cmin[xx]+V[xx][i].c;
                 fol[V[xx][i].v]++;
                 if (fol[V[xx][i].v]>n-1)
                 {negativ=1;break;}
                 Q.push(V[xx][i].v);
                }
         if (negativ) break;
        }
    if (negativ)
        fprintf(fout,"Ciclu negativ!\n");
        else for (int i=2;i<=n;i++) fprintf(fout,"%d ",cmin[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}