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

queue< pair<int,int> > Q;
vector <int> G[maxn],C[maxn];
int d[maxn],nr[maxn];
int ok,n,m,x,y,c;
void BELL(){
    Q.push(make_pair(1,0));
    nr[1]=1;
    for(int i=2;i<=n;++i)
        d[i]=inf;
    pair<int,int> A;
    while(!Q.empty() && ok){
        A=Q.front(); Q.pop();

        int nod=A.first;
        int cost=A.second;
        for(int i=0;i<G[nod].size();++i){
            int y=G[nod][i];
            if(d[y]>C[nod][i]+cost){
                d[y]=C[nod][i]+cost;
                 Q.push(make_pair(y,d[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;
}