#include<cstdio>
#include<vector>
#define maxn 50003
#define inf 2000000003
#include<queue>
using namespace std;

queue <int>  Q;
vector <int> G[maxn],C[maxn];
int d[maxn],nr[maxn];
int ok,n,m,x,y,c;
void BELL(){
    Q.push(1);
    nr[1]=1;
    for(int i=2;i<=n;++i)
        d[i]=inf;

    while(!Q.empty() && ok){

        int nod=Q.front();
        Q.pop();
        for(int i=0;i<G[nod].size();++i){
            int y=G[nod][i];
            if(d[y]>C[nod][i]+d[nod]){
                d[y]=C[nod][i]+d[nod];
                 Q.push(y);
                ++nr[y];
            }
            if(nr[y]==n){
                printf("Ciclu negativ!");
                ok=0;
                break;

            }
        }
    }
}
int main(){
    ok=1;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back(y);
        C[x].push_back(c);
    }
    BELL();
    if(ok)
        for(int i=2;i<=n;++i)
            printf("%d ",d[i]);
    return 0;
}