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

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;
    counter[1]++;
    coada.push(1);
    while(!coada.empty()){
        int i=coada.front();
        coada.pop();
        for(int j=0; j<g[i]; j++)
            if(counter[nod[i][j].v]>n){
                cout<<"Ciclu negativ!";
                return;
        }
           else if(distanta[nod[i][j].v]>distanta[i]+nod[i][j].w){
                distanta[nod[i][j].v]=distanta[i]+nod[i][j].w;
                coada.push(nod[i][j].v);
                counter[nod[i][j].v]++;
            }
    }
    for(int i=2; i<=n; i++)
        cout<<distanta[i]<<' ';
}

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