#include <cstdio>
#include<vector>
#include<bitset>
#include<queue>
#define maxn 50005
#define INF 200000005
using namespace std;

FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");
vector <int> G[maxn],C[maxn],nrcoada(maxn),d(maxn,INF);
bool negative=false;
queue <pair <int,int> > Q;
bitset <maxn> incoada;
int n,m,x,y,c;
void bellman(){
    Q.push(make_pair(1,0)); //nod si cost
    d[1]=0;

    while(Q.empty()==0 && negative==false){
        pair <int,int > A=Q.front();
        Q.pop();
        int nod=A.first;
        int cost=A.second;

        for(int i=0;i<G[nod].size();i++){
            if(d[nod]!=INF){
            int vecin=G[nod][i];
            if(d[vecin]>cost+C[nod][i]){
                d[vecin]=cost+C[nod][i];

                if(nrcoada[vecin]==n)
                    negative=true;
                else
                {
                    Q.push(make_pair(vecin,C[nod][i]));
                    nrcoada[vecin]++;
                }
            }
            }
        }
    }
}

int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++){
            fscanf(f,"%d%d%d",&x,&y,&c);
        G[x].push_back(y);
        C[x].push_back(c);
    }
    bellman();
    if(negative==true)
        fprintf(g,"Ciclu negativ!");
    else
        for(int i=2;i<=n;i++)
            fprintf(g,"%d ",d[i]);
    return 0;
}