#include <fstream>
#include <vector>
using namespace std;

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

const int N = 5e4 + 1, M = 25e4 + 1, inf = 1e3 + 1;
vector <int> dist(N);
bool cycle;
int n, m;

struct edge
{
    int f, s, w;
}e[M];

void BellmanFord(edge v[], int src)
{
    int i, j;
    dist = vector <int> (n + 1, inf);
    dist[src] = 0;

    for(i = 1; i < n; ++ i)
        for(j = 1; j <= m; ++ j)
        {
            if(e[i].s == src) continue;
            if(dist[e[j].s] > dist[e[j].f] + e[j].w)
                dist[e[j].s] = dist[e[j].f] + e[j].w;
        }

    for(j = 1; j <= m; ++ j)
        if(dist[e[j].s] > dist[e[j].f] + e[j].w)
            {cycle = 1; return;}
}

int main()
{
    int i;
    in >> n >> m;

    for(i = 1; i <= m; ++ i)
        in >> e[i].f >> e[i].s >> e[i].w;

    BellmanFord(e, 1);

    if(cycle)
        out << "Ciclu negativ!";

    else
        for(i = 2; i <= n; ++ i)
            out << dist[i] << ' ';

    return 0;
}