#include <fstream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <limits>
#include <utility>
#include <queue>

typedef std::pair<unsigned short, signed short> vertex;
typedef std::list<vertex> edge;
typedef std::vector<edge> graph;

void BellmanFord (const graph &g, std::vector<signed int> &shortest_path)
{
    unsigned int size(g.size());
    unsigned short node, neighbor;
    signed int distance, new_distance;
    edge::const_iterator iterator, end;
    std::vector<bool> availeable(size,true);
    availeable[0] = false;
    std::vector<unsigned short> total_updates(size,0);
    total_updates[0] = 1;
    std::queue<unsigned short> update;
    update.push(0);
    do
    {
        node = update.front();
        update.pop();
        distance = shortest_path[node];
        availeable[node] = true;
        for (iterator = g[node].begin(), end = g[node].end() ; iterator != end ; ++iterator)
        {
            neighbor = iterator->first;
            new_distance = distance + iterator->second;
            if (new_distance < shortest_path[neighbor])
            {
                ++total_updates[neighbor];
                if (total_updates[neighbor] == size)
                    throw std::string("Ciclu negativ!");
                shortest_path[neighbor] = new_distance;
                if (availeable[neighbor])
                {
                    availeable[neighbor] = false;
                    update.push(neighbor);
                }
            }
        }
    }
    while (!update.empty());
}

int main (void)
{
    unsigned int n,m;
    std::ifstream input("bellmanford.in");
    input >> n >> m;
    graph g(n);
    unsigned short node1, node2;
    signed short path;
    do
    {
        input >> node1 >> node2 >> path;
        g[node1 - 1].push_front(std::make_pair(node2 - 1,path));
        --m;
    }
    while (m);
    input.close();
    static const signed int LONGEST_POSSIBLE_PATH(std::numeric_limits<signed int>::max());
    std::vector<signed int> shortest_path(n,LONGEST_POSSIBLE_PATH);
    shortest_path[0] = 0;
    try
    {
        BellmanFord(g,shortest_path);
    }
    catch (const std::string &error_message)
    {
        std::ofstream output("bellmanford.out");
        output << error_message << '\n';
        output.close();
        return 0;
    }
    {
        std::ofstream output("bellmanford.out");
        std::vector<signed int>::const_iterator iterator(&shortest_path[1]), end(shortest_path.end());
        while (true)
        {
            output << *iterator;
            ++iterator;
            if (iterator == end)
                break;
            output.put(' ');
        }
        output.put('\n');
        output.close();
    }
    return 0;
}