#include <fstream>

using namespace std;
#define inf 2000000000
struct muchie
{
    int src,dest,cost;
};
muchie v[250005];
int dist[50003];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int main()
{
    int n,m,i,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].src>>v[i].dest>>v[i].cost;
    }
    for(i=1;i<=n;i++)
    {
        dist[i]=inf;
    }
    dist[1]=0;
    for(j=1;j<=n-1;j++)
    {
        for(i=1;i<=m;i++)
            if(dist[v[i].dest]>dist[v[i].src]+v[i].cost)
            {
                dist[v[i].dest]=dist[v[i].src]+v[i].cost;
            }
    }
    int ok=1;
    for(i=1;i<=m;i++)
        if(dist[v[i].src]+v[i].cost<dist[v[i].dest])
        {ok=-1;i=m+2;}
    if(ok==-1)
        g<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            g<<dist[i]<<" ";
    return 0;
}