#include <fstream>
#include <list>
#define oo 0x3f3f3f3f
using namespace std;

class edge
{
public:
    int x;
    int y;
    int w;
    friend ifstream& operator>>(ifstream& in, edge& e);
};

ifstream& operator>>(ifstream& in, edge& e) {
        in>>e.x>>e.y>>e.w;
        return in;
    }

inline bool relax(edge &e, int dist[])
{
    if (dist[e.y] > dist[e.x] + e.w) {
        dist[e.y] = dist[e.x] + e.w;
        return true;
    }
    return false;
}

bool relax(list<edge> &edges, int dist[])
{
    bool did_smth = false;
    for(list<edge>::iterator it = edges.begin(); it != edges.end(); ++it)
        did_smth = relax(*it, dist) || did_smth;
    return did_smth;
}

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    int i, V, E;
    edge e;
    list<edge> edges;

    in>>V>>E;
    for (i = 0; i < E; i++) {
        in>>e;
        edges.push_back(e);
    }

    int dist[V + 1];
    dist[1] = 0;
    for(i = 2; i <= V; i++) {
        dist[i] = oo;
    }

    for(i = 1; i <= V - 1; i++)
        if (!relax(edges, dist))
            break;

    if (relax(edges, dist))
        out<<"Ciclu negativ!";
    else
        for (i = 2; i <= V; i++)
            out<<dist[i]<<" ";

    return 0;
}