#include <bits/stdc++.h>

using namespace std;

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


class Node
{
public:
    int node;
    int cost;

public:

    void initialize(const int n, const int c)
    {
        node = n;
        cost = c;
    }

    Node()
    {}

    Node(const int n, const int c)
    {
        initialize(n, c);
    }

    ~Node()
    {}
};

vector <int> bellman(int start, vector <vector <Node>> &path)
{
    vector <int> dist(path.size(), numeric_limits<int>::max());

    queue <int> q;
    vector <bool> in_q(path.size(), false);

    vector <int> update(path.size(), 0);


    int current;
    Node vec;

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

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

        for(unsigned i = 0; i < path[current].size(); i++)
        {
            vec = path[current][i];

            if(dist[vec.node] > dist[current] + vec.cost)
            {
                dist[vec.node] = dist[current] + vec.cost;
                update[vec.node]++;

                if((unsigned)update[vec.node] >= path.size())
                {
                    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 <Node>> path(n + 1);

    int x, y, c;

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

    vector <int> ans = bellman(1, path);
    if(ans.size())
        for(int i = 2; i <= n; i++)
            if(ans[i] == numeric_limits<int>::max())
                fout<<0<<' ';
            else
                fout<<ans[i]<<' ';
    else
        fout<<"Ciclu negativ!\n";
    return 0;
}