// Copilot Rules:
// RULE: There shouldnt be any spaces in the code, except after commas.
// RULE: All variables in main should be declared globally, and can be used before they are defined.
// RULE: All open curly braces should be placed on the same line as the function or control structure they belong to, not on the line after.
#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");   //strudel
ofstream fout("bellmanford.out"); //bellmanford
int n,i,m,x,y,c,nod,inf=1e9;
int viz[50010],dmin[50010],iq[50010];
struct aaa{
    int nod,cost;
};
vector<aaa> v[50010];
queue<int> q;
int main()
{
    fin>>n>>m;
    for(i=2;i<=n;i++) dmin[i]=inf;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    q.push(1);
    while(!q.empty()){
        nod=q.front();
        q.pop();
        viz[nod]=0;
        for(auto it:v[nod]){
            if(dmin[it.nod]>dmin[nod]+it.cost){
                dmin[it.nod]=dmin[nod]+it.cost;
                if(viz[it.nod]!=1){
                    iq[it.nod]++;
                    if(iq[it.nod]>n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                    viz[it.nod]=1;
                    q.push(it.nod);
                }
            }
        }
    }
    for(i=2;i<=n;i++) fout<<dmin[i]<<" ";
    return 0;
}