#include <cstdio>
#include<vector>
#define MAX_N 50001
#define inf 250000000
using namespace std;
int N, M, dist[MAX_N], c[MAX_N], p, u, contor[MAX_N];
bool isinc[MAX_N];
vector<pair <int, int> > graph[MAX_N];
FILE *f, *g;
int main()
{
    int ok=1;

    f = fopen("bellmanford.in", "r");
    g = fopen("bellmanford.out", "w");

    fscanf(f, "%d%d", &N, &M);
    for(int i=0; i<M; i++)\
    {
        int x, y, c;
        fscanf(f, "%d%d%d", &x, &y, &c);
        graph[x].push_back(make_pair(y, c));
    }

    p=1;
    u=1;
    c[p]=1;
    for(int i=2; i<=N; i++)
        {dist[i]=inf;
        isinc[i]=true;
        u++;
        c[u]=i;
        contor[i]++;
        }
    while(p<=u && ok)
    {
        int x=c[p];
        isinc[x]=false;
        for(int i=0; i<graph[x].size(); i++)
        {
            int vecin=graph[x][i].first;
            int cost=graph[x][i].second;
            if(dist[vecin]>dist[x]+cost)
            {
                dist[vecin]=dist[x]+cost;
                if(isinc[vecin]==false)
                {
                    isinc[vecin]=true;
                    u++;
                    c[u]=vecin;
                    contor[vecin]++;
                }
            }
            if(contor[vecin]>N+1)
                ok=0;
        }
        p++;
    }

    if(ok==0)
        fprintf(g, "Ciclu negativ!");
    else
        for(int i=2; i<=N; i++)
            fprintf(g, "%d ", dist[i]);
    fclose(f);
    fclose(g);
    return 0;
}