#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
#define dim 50001
#define inf 1000000000
#define x first
#define y second
using namespace std;

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

int n,m,i,j,nod,vec,cost,d[dim],cnt[dim];
vector <pair <int,int> > l[dim];
bitset <dim> f;
deque <int> q;

int main(){
    fin>>n>>m;

    for(i=2;i<=n;i++)
        d[i]=inf;

    for(;m;m--){
        fin>>i>>j>>cost;
        l[i].push_back(make_pair(j,cost));
    }

    q.push_back(1);

    while(!q.empty()){
        nod=q.front();
        q.pop_front();
        f[nod]=0;

        for(i=0;i<l[nod].size();i++){
            vec=l[nod][i].x;
            cost=l[nod][i].y;

            if(d[vec]>d[nod]+cost){
                d[vec]=d[nod]+cost;

                if(f[vec]==0){
                    f[vec]=1;
                    q.push_back(vec);
                    if(++cnt[vec]==n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";

    return 0;
}