#include <cstdio>
#include <vector>
#include <queue>
#define f first
#define s second
#define pb push_back
#define mp make_pair
const int NOD = 250555;
const int INF = 1<<30;
using namespace std;
typedef pair < int,int > P;
vector <P> gr[NOD];
int viz[NOD],n;
long long d[NOD];
queue <int> coada;
int bellman_ford();
int main()
{
    int m;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;--m){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        gr[x].pb(mp(y,c));
    }
    for(int i=2;i<=n;d[i]=INF,++i);
    if(bellman_ford()){
        printf("Ciclu negativ!\n");
    }
    else{
        for(int i=2;i<=n;++i)printf("%d ",d[i]);
        printf("\n");
    }
    return 0;
}
int bellman_ford(){
    coada.push(1);
    viz[1]=1;
    while(!coada.empty()){
        int fata=coada.front();
        coada.pop();
        for(int i=0;i<(int)gr[fata].size();++i){
            int next=gr[fata][i].f;
            int cost=gr[fata][i].s;
            if(d[fata]+cost<d[next]){
                d[next]=d[fata]+cost;
                viz[next]=viz[fata]+1;
                coada.push(next);
                if(viz[next]==n)return 1;
            }
        }
    }
    return 0;
}