#include<fstream>
#include<vector>
using namespace std;
#define maxn 50005
#define inf 1000000000
int n,m,distanta[maxn],g[maxn];
struct nou{
    int w,v;
};
vector <nou> nod[maxn];

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

void read(){
    cin>>n>>m;
    int x;
    nou y;
    for(int i=1; i<=m; i++){
        cin>>x>>y.v>>y.w;
        nod[x].push_back(y);
        g[x]++;
    }
}

void solve(){

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

    for(int i=1; i<n; i++)
        for(int j=0; j<g[i]; j++)
            if(distanta[nod[i][j].v]>distanta[i]+nod[i][j].w)
                distanta[nod[i][j].v]=distanta[i]+nod[i][j].w;
     for(int i=1; i<=n; i++)
        for(int j=0; j<g[i]; j++)
            if(distanta[i]+nod[i][j].w<distanta[nod[i][j].v]){
                cout<<"Ciclu negativ!";
                return;
            }
    for(int i=2; i<=n; i++)
        cout<<distanta[i]<<' ';
}

int main(){
    read();
    solve();
}