#include <cstdio>
#include <vector>
#include <queue>
#include <climits>

#define inf INT_MAX/2

using namespace std;

struct nod{
    int d;
    int nrvis;
    bool in_queue;
    vector<pair<nod*, int> > vecini;
};

int main()
{
    bool neg_cycle=false;
    nod v[50000];
    FILE* f=fopen("bellmanford.in", "r");
    int n, m;
    fscanf(f, "%d%d", &n, &m);

    for(int i=1;i<=n;i++){
        v[i].d=inf;
        v[i].in_queue=false;
        v[i].nrvis=0;
    }

    for(int i=0;i<m;i++){
        int x, y, c;
        fscanf(f, "%d%d%d", &x, &y, &c);
        v[x].vecini.push_back(make_pair(&v[y], c));
    }

    queue<nod*> q;
    q.push(&v[1]);
    v[1].d=0;
    v[1].in_queue=true;
    v[1].nrvis++;

    while(!q.empty()){
        nod* x=q.front();
        q.pop();
        x->in_queue=false;

        if(x->nrvis>n){
            neg_cycle=true;
            break;
        }

        for(vector<pair<nod*, int> >::iterator it=x->vecini.begin();it!=x->vecini.end();it++){
            if(it->first->d > x->d+it->second){
                it->first->d=x->d+it->second;
                if(!it->first->in_queue){
                    it->first->in_queue=true;
                    it->first->nrvis++;
                    q.push(it->first);
                }
            }
        }
    }

    f=fopen("bellmanford.out", "w");

    if(!neg_cycle)
        for(int i=2;i<=n;i++)
            fprintf(f, "%d ", v[i].d);
    else
        fprintf(f,"Ciclu negativ!");
    return 0;
}