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

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, const signed int longest_possible_path)
{
    unsigned short size(g.size()), node, neighbor;
    signed int distance, new_distance;
    bool not_updated;
    edge::const_iterator iterator, end;
    for (unsigned short update(1) ; update < size; ++update)
    {
        not_updated = true;
        for (node = 0 ; node < size ; ++node)
        {
            distance = shortest_path[node];
            if (distance == longest_possible_path)
                continue;
            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])
                {
                    shortest_path[neighbor] = new_distance;
                    not_updated = false;
                }
            }
        }
        if (not_updated)
            return;
    }
    for (node = 0 ; node < size ; ++node)
    {
        distance = shortest_path[node];
        if (distance == longest_possible_path)
            continue;
        for (iterator = g[node].begin(), end = g[node].end() ; iterator != end ; ++iterator)
        {
            new_distance = distance + iterator->second;
            if (new_distance < shortest_path[iterator->first])
                throw std::string("Ciclu negativ!");
        }
    }
}

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,LONGEST_POSSIBLE_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;
}