#include<cstdio>
#include<queue>
#include<vector>
#define INF 2e9
using namespace std;
struct muchie{int nod,cost;};
vector <muchie> g[50001];
char in[50001];
char ap[50001];
int best[50001];
queue <int> d;
int main(){
    int n,m,i,a,b,c,nod;
    muchie x,it;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        x.nod=b;
        x.cost=c;
        g[a].push_back(x);
    }
    for(i=2;i<=n;i++)
        best[i]=INF;
    best[1]=0;
    in[1]=1;
    ap[1]=1;
    d.push(1);
    while(!d.empty()){
        nod=d.front();
        d.pop();
        in[nod]=0;
        for(i=0;i<g[nod].size();i++){
            it=g[nod][i];
            if(best[it.nod]>best[nod]+it.cost){
                best[it.nod]=best[nod]+it.cost;
                if(!in[it.nod]){
                    d.push(it.nod);
                    in[it.nod]=1;
                    ap[it.nod]++;
                    if(ap[it.nod]==n+1){
                        printf("Ciclu negativ!");
                        return 0;
                    }
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        printf("%d ",best[i]);
    return 0;
}