#include <fstream>
#include <vector>
#include <queue>
#define INF 50000001

using namespace std;

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

queue <int>q;
vector < pair<int,int> > l[50010];

int f[50010],d[50010];
int x,y,n,m,i,c;

int bfs(){

    q.push(1);

    while (q.size()) {
        x=q.front();
        f[x]++;
        if (f[x]==n){
            fout<<"Ciclu negativ!\n";
            return 0;
        }
        for (int i=0;i<l[x].size();i++) {
            if (d[x]+l[x][i].second < d[l[x][i].first]){
                d[l[x][i].first]=d[x]+l[x][i].second;
                q.push(l[x][i].first);
            }
        }
        q.pop();
    }
    return 1;
}

int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        l[x].push_back(make_pair(y,c));
    }

    for (i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;

    if (bfs()) {
        for (i=2;i<=n;i++)
            fout<<d[i]<<" ";
    }

    return 0;
}