#include <fstream>
#include <vector>

#define NLen 65536
#define MLen 262144
#define inf 0x7fffffff

using namespace std;

ifstream fi;
ofstream fo;

struct triple
{
    int x, y, c;
};

vector < triple > ed;
int cost[NLen];

inline triple mk(int x, int y, int c)
{
    triple ret;

    ret.x = x;
    ret.y = y;
    ret.c = c;

    return ret;
}

int main()
{
    int M, N, x, y, c;

    fi.open("bellmanford.in");

    fi >> N >> M;
    for( ;M -- ;)
    {
        fi >> x >> y >> c;
        ed.push_back(mk(x, y, c));
    }

    fi.close();

    cost[1] = 0;
    for(int i = 2;i <= N; ++ i)
        cost[i] = inf;

    for(int i = 1;i < N; ++ i)
        for(int j = 0;j < ed.size(); ++ j)
            if(cost[ ed[j].x ]!= inf)
                if(cost[ ed[j].y ] > cost[ ed[j].x ] + ed[j].c)
                    cost[ ed[j].y ] = cost[ ed[j].x ] + ed[j].c;

    int neg = 0;
    for(int i = 0;i < ed.size(); ++ i)
        if(cost[ ed[i].y ] > cost[ ed[i].x ] + ed[i].c)
        {
            neg = 1;
            break;
        }

    fo.open("bellmanford.out");

    if(neg) fo << "Ciclu negativ!\n";
    else
    {
        for(int i = 2;i <= N; ++ i)
            fo << cost[i] << ' ';
        fo << '\n';
    }

    fo.close();

    return 0;
}