#include <bits/stdc++.h>

using namespace std;

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

class Edge
{
public:
    int node;
    int cost;

    Edge()
    {}

    Edge(int n, int c)
    {
        node = n;
        cost = c;
    }
};

class comp
{
public:
    bool operator()(Edge a, Edge b)
    {
        return a.cost > b.cost;
    }
};

vector <int> Bellman(int start, vector <vector <Edge>> &path)
{
    int n = path.size();

    vector <int> dist(n, numeric_limits<int>::max());
    vector <int> updated(n, 0);

    queue <int> q;
    vector <bool> in_q(n, false);

    int now;
    Edge vec;

    dist[start] = 0;
    q.push(start);
    in_q[start] = true;

    while(!q.empty())
    {
        now = q.front();
        q.pop();
        in_q[now] = false;

        for(unsigned i = 0; i < path[now].size(); i++)
        {
            vec = path[now][i];
            if(dist[vec.node] > dist[now] + vec.cost)
            {
                dist[vec.node] = dist[now] + vec.cost;
                updated[vec.node]++;


                if(updated[vec.node] >= n)
                {
                    vector <int> a;
                    return a;
                }

                if(!in_q[vec.node])
                {
                    q.push(vec.node);
                    in_q[vec.node] = true;
                }
            }
        }
    }

    return dist;
}

int main()
{
    int n, m;
    fin>>n>>m;

    vector <vector <Edge>> path(n + 1);

    int x, y, c;

    for(; m; m--)
    {
        fin>>x>>y>>c;
        path[x].push_back(Edge(y, c));
    }

    vector <int> dist = Bellman(1, path);

    if(dist.size())
    {
        for(int i = 2; i <= n; i++)
            fout<<dist[i]<<' ';
    }
    else
        fout<<"Ciclu negativ!\n";

    return 0;
}