#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

#define limn 50010
#define inf 2e9

int n, m, viz[limn], nod;
vector < pair <int, int> > G[limn];
int path[limn];
queue < int > q;

void read(){
    int x, y, c;
    fin>>n>>m;
    while(m--){
        fin>>x>>y>>c;
        G[x].push_back({y,c});
    }
}

int main(){
    read();
    for (int i=2; i<=n; i++){
        path[i] = inf;
    }
    path[1] = 0;
    q.push(1);

    while (!q.empty()){
        nod = q.front();
        q.pop();
        viz[nod]++;
        if (viz[nod] > n){
            fout<<"Ciclu negativ!";
            return 0;
        }
        for (auto it:G[nod]){
            if (path[it.first] > path[nod] + it.second){
                path[it.first] = path[nod] + it.second;
                q.push (it.first);
            }
        }
    }
    for (int i=2; i<=n; i++)
        fout<<path[i]<<' ';


    fout.close();
    return 0;
}