#include <stdio.h>
#include <vector>
#include <bitset>
#include <queue>
#define nmax 50010
#define inf 0x3f3f3f3f
using namespace std;
int n,m,i,j,x,y,z,d[nmax],fr[nmax];
vector <pair<int,int> > g[nmax];
queue <int> que;
int main() {
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++) {
    scanf("%d %d %d",&x,&y,&z);
    g[x].push_back(make_pair(y,z));
}
for (i=1;i<=n;i++) d[i]=inf;
que.push(1); d[1]=0;
while (!que.empty()) {
    x=que.front(); que.pop();
    for (i=0;i<g[x].size();i++)
        if (d[g[x][i].first]>d[x]+g[x][i].second) {
            if (fr[g[x][i].first]==n) {
                puts("Ciclu negativ!"); return 0;
            }
            d[g[x][i].first]=d[x]+g[x][i].second; fr[g[x][i].first]++;
            que.push(g[x][i].first);
    }
}
for (i=2;i<=n;i++) printf("%d ",d[i]);
return 0;
}