#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int nmax= 50000, inf= 1<<30;

struct str{
    int x, y;
};

vector <str> g[nmax+1];
bool uq[nmax+1];
int cnt[nmax+1], bf[nmax+1];
queue <int> q;

int main(){
    int n, m;

    fin>>n>>m;
    for (int i= 1; i<=m; ++i){
        int x;
        str aux;
        fin>>x>>aux.x>>aux.y;
        g[x].push_back(aux);
    }

    for (int i= 2; i<=n; ++i){
        bf[i]= inf;
    }
    q.push(1); uq[1]= 1;
    bool nc= 0;
    while (!q.empty()&& !nc){
        int x= q.front();
        q.pop(); uq[x]= 0;

        for (vector <str>::iterator it= g[x].begin(); it!=g[x].end(); ++it){
            if (bf[it->x]>bf[x]+(it->y)){
                bf[it->x]= bf[x]+(it->y);
                
                if (!uq[it->x]){
                    q.push(it->x); uq[it->x]= 1;
                    ++cnt[it->x];
                    if (cnt[it->y]>n){
                        nc= 1;
                        break;
                    }
                }
            }
        }
    }

    if (nc){
        fout<<"Ciclu negativ!";
    }else{
        for (int i= 2; i<=n; ++i){
            fout<<bf[i]<<" ";
        }
        fout<<"\n";
    }

    return 0;
}