#include <fstream>
#include <queue>
#include <vector>
#define n_max 50002
#define inf 0x3f3f3f3f

using namespace std;

ifstream r("bellmanford.in");
ofstream w("bellmanford.out");

vector < pair <int,int> > G[n_max];
queue <int> Q;
int viz[n_max],nr[n_max],d[n_max];
int n,m;

void read() {
    int i,j,k,c;
    r>>n>>m;
    for (k=1; k<=m; k++) {
        r>>i>>j>>c;
        G[i].push_back(make_pair(j,c));
    }
}

bool bellman_ford() {
    int prec,i;
    for (i=1; i<=n; i++)
        d[i]=inf;
    d[1]=0;
    Q.push(1);
    while (!Q.empty()) {
        prec=Q.front();
        Q.pop();
        viz[prec]=0;
        for (vector < pair <int,int> >::iterator it=G[prec].begin(); it!=G[prec].end(); it++)
            if (d[prec]+it->second<d[it->first]){
                d[it->first]=d[prec]+it->second;
                if (viz[it->first]==0) {
                    if (nr[it->first]>n-1)
                        return false;
                    else {
                        viz[it->first]=1;
                        Q.push(it->first);
                        nr[it->first]++;
                    }
                }
            }
    }
    return true;
}

int main () {
    read();
    if (bellman_ford())
        for (int i=2; i<=n; i++)
            w<<d[i]<<" ";
    else
        w<<"Ciclu negativ!";
    r.close();
    w.close();
    return 0;
}