#include<stdio.h>
#include<vector>
#include<utility>
#include<queue>
using namespace std;

vector<pair<int,int> > m[55000];
int N,M,x,y,z,cnt[55000],d[55000];
queue<int> q;

int main() {
    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,&z);
        m[x].push_back(make_pair(y,z));
    }
    q.push(1);
    for(int i=2;i<=N;++i) {
        d[i] = 1000000000;
    }
    while(!q.empty()) {
        x = q.front();
        ++cnt[x];
        if(cnt[x]>N) {
            printf("Ciclu negativ!");
            return 0;
        }
        q.pop();
        for(int i=0;i<m[x].size();++i) {
            y = m[x][i].first;
            z = m[x][i].second;
            if(d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push(y);
            }
        }
    }
    for(int i=2;i<=N;++i) {
        printf("%d ",d[i]);
    }
    return 0;
}