#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct elem
{
    int nod, c;
};

vector <elem> a[50001];
queue <int> q;

int d[50001],nr[50001],n,m,inq[50001];
bool ok=1;

int main()
{int x,y,z,l;
f>>n>>m;
for (int i=1;i<=m;i++) {f>>x>>y>>z;
                        a[x].push_back({y,z});

                       }
for (int i=1;i<=n;i++) d[i]=INF;
d[1]=0;
q.push(1);
inq[1]=1;
nr[1]=1;
while (ok==1 && !q.empty())
{x=q.front();
q.pop();
inq[x]=0;
l=a[x].size();
for (int i=0;i<l;i++) if (d[a[x][i].nod]>d[x]+a[x][i].c) {d[a[x][i].nod]=d[x]+a[x][i].c;
                                                      if (inq[a[x][i].nod]==0) {q.push(a[x][i].nod);
                                                                            inq[a[x][i].nod]=1;
                                                                            nr[a[x][i].nod]++;
                                                                            if (nr[a[x][i].nod]==n) {ok=0; break;}
                                                                           }
                                                      }
}
if (ok==0) g<<"Ciclu negativ!";
    else for (int i=2;i<=n;i++) g<<d[i]<<' ';
}