#include<cstdio>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;

int d[50005],ciclu[50005];
int n,m,x,y,ok,cost;
queue <int>q;
vector <int> g[50005], c[50005];
int bellmanford(int x0){
    for(int i=1;i<=n;++i)
        d[i]=inf;
    d[x0]=0;
    q.push(x0);
    while(!q.empty()){
        int x=q.front();
        ciclu[x]++;
        if(ciclu[x]>n){
            return -1;
        }
        for(int i=0;i<g[x].size(); ++i)
            if(d[g[x][i]] > d[x] + c[x][i]) {
                ///relaxare muchii
                d[g[x][i]] = d[x] + c[x][i];
                q.push(g[x][i]);
            }
        q.pop();
    }
    return 1;
}
int main()
{
    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,&cost);
        g[x].push_back(y);
        c[x].push_back(cost);
    }
    ok=bellmanford(1);
    if(ok==-1) printf("Ciclu negativ!");
    else{
        for(int i=2;i<=n;i++){
           printf("%d ",d[i]);
        }
    }

}