#include <iostream>
#include <fstream>
#include <vector>

std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");

struct edge
{
    int from;
    int to;
    int cost;
};

const int N=50000;
const int M=250000;
const int INF=9000000;

int d[N+1];
edge g[M+1];

int n, m;

int main()
{
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>g[i].from>>g[i].to>>g[i].cost;
    }

    for(int i=1; i<=n; i++) d[i]=INF;
    d[1]=0;

    for(int pas=1; pas<=n-1; pas++)
    {
        for(int i=1; i<=m; i++)
        {
            if(d[g[i].from]+g[i].cost<d[g[i].to])
            {
                d[g[i].to]=d[g[i].from]+g[i].cost;
            }
        }
    }

    for(int pas=1; pas<=n-1; pas++)
    {
        for(int i=1; i<=m; i++)
        {
            if(d[g[i].from]+g[i].cost<d[g[i].to])
            {
                out<<"Ciclu negativ!";
                return 0;
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
       out<<d[i]<<" ";
    }
}