#include <cstdio>
#include <vector>
#include <deque>
#define MAX 50001
#define INF 0xEEA8310

using namespace std;
vector<pair<int,int> >u[MAX];
deque<int>s,d;

int dist[MAX],n,m;
int viz[MAX];

void bellman_ford(){
    int k,i,x;
    dist[1]=0;
    viz[1]=1;
    s.push_back(1);
    for(k=1;k<=n;k++){
        while(s.size()>0){
        x=s.front();
        viz[x]--;
        if(viz[x]==0)
        for(i=0;i<u[x].size();i++)
        if(dist[x]+u[x][i].second<dist[u[x][i].first]){
            dist[u[x][i].first]=dist[x]+u[x][i].second;
            viz[u[x][i].first]++;
            d.push_back(u[x][i].first);}
        s.pop_front(); }
        swap(s,d);
        }
    if(s.size()>0)printf("Ciclu negativ!\n"); else {
        for(i=2;i<=n;i++)printf("%d ",dist[i]); }
}

int main(){
    int x,y,c;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&c);
        u[x].push_back(make_pair(y,c)); }
        for(int i=1;i<=n;i++)dist[i]=INF;
    bellman_ford();
}