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

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;

char *buffer;

void read_int(int &x){
    while (*buffer!='-'&& (*buffer<'0'|| *buffer>'9')){
        ++buffer;
    }

    int sign;
    if (*buffer=='-'){
        sign= -1;
        ++buffer;
    }else{
        sign= 1;
    }

    x= 0;
    while (*buffer>='0'&& *buffer<='9'){
        x= x*10 +sign*(*buffer-'0');
        ++buffer;
    }
}

int main(){
    int fs;
    fin.seekg(0, ios_base::end);
    fs= fin.tellg();
    fin.seekg(0, ios_base::beg);
    buffer=(char *)malloc(fs);
    fin.getline(buffer, fs, EOF);

    int n, m;
    read_int(n); read_int(m);
    for (int i= 1; i<=m; ++i){
        int x;
        str aux;
        read_int(x); read_int(aux.x); read_int(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;
}