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

typedef std::pair<unsigned int, unsigned int> data; // vertex, distance
typedef std::list<data> edge;
typedef std::vector<edge> graph;

inline void heap_up (std::vector<unsigned int> &min_heap, std::vector<unsigned int> &min_distance, std::vector<unsigned int> &heap_index, unsigned int index)
{
    unsigned int father(index >> 1), vertex(min_heap[index]), distance(min_distance[min_heap[index]]);
    while (distance < min_distance[min_heap[father]])
    {
        std::swap(heap_index[vertex],heap_index[min_heap[father]]);
        min_heap[index] = min_heap[father];
        index = father;
        if (father > 1)
            father >>= 1;
        else
            break;
    }
    min_heap[index] = vertex;
}

inline void heap_down (std::vector<unsigned int> &min_heap, std::vector<unsigned int> &min_distance, std::vector<unsigned int> &heap_index, unsigned int index)
{
    unsigned int left(index << 1), right(left + 1), size(min_heap.size()), smallest;
    while (true)
    {
        if (left < size && min_distance[min_heap[left]] < min_distance[min_heap[index]])
            smallest = left;
        else
            smallest = index;
        if (right < size && min_distance[min_heap[right]] < min_distance[min_heap[smallest]])
            smallest = right;
        if (smallest == index)
            break;
        std::swap(heap_index[min_heap[index]],heap_index[min_heap[smallest]]);
        std::swap(min_heap[index],min_heap[smallest]);
        index = smallest;
        left = index << 1;
        right = left + 1;
    }
}

inline void pop_heap (std::vector<unsigned int> &min_heap, std::vector<unsigned int> &min_distance, std::vector<unsigned int> &heap_index)
{
    heap_index[min_heap.back()] = 1;
    min_heap[1] = min_heap.back();
    min_heap.pop_back();
    heap_down(min_heap,min_distance,heap_index,1);
}

inline void Dijkstra (graph &g, std::vector<unsigned int> &min_distance)
{
    std::vector<unsigned int> heap_index(g.size());
    for (unsigned int iterator(1), end(g.size()) ; iterator < end ; ++iterator)
        heap_index[iterator] = iterator;
    std::vector<unsigned int> min_heap(heap_index.begin(),heap_index.end());
    min_distance[1] = 0;
    edge::iterator iterator, end;
    unsigned int new_distance, distance, min;
    do
    {
        min = min_heap[1];
        distance = min_distance[min];
        pop_heap(min_heap,min_distance,heap_index);
        if (distance == -1)
        {
            if (min_heap.size() == 1)
                break;
            else
                continue;
        }
        for (iterator = g[min].begin(), end = g[min].end() ;  iterator != end ; ++iterator)
        {
            new_distance = distance + iterator->second;
            if (new_distance < min_distance[iterator->first])
            {
                min_distance[iterator->first] = new_distance;
                if (heap_index[iterator->first] > 1 && new_distance < min_distance[min_heap[heap_index[iterator->first] >> 1]])
                    heap_up(min_heap,min_distance,heap_index,heap_index[iterator->first]);
            }
        }
    }
    while (min_heap.size() > 1);
}

int main (void)
{
    std::ifstream input("dijkstra.in");
    unsigned int n,m;
    input >> n >> m;
    ++n;
    unsigned int node1, node2, distance;
    graph g(n);
    do
    {
        input >> node1 >> node2 >> distance;
        g[node1].push_front(std::make_pair(node2,distance));
        --m;
    }
    while (m);
    input.close();
    std::vector<unsigned int> min_distance(n,-1);
    Dijkstra(g,min_distance);
    {
        std::ofstream output("dijkstra.out");
        std::vector<unsigned int>::const_iterator iterator(&min_distance[2]), end(min_distance.end());
        while (true)
        {
            if (*iterator == -1 || *iterator == 0)
                output.put('0');
            else
                output << *iterator;
            ++iterator;
            if (iterator == end)
                break;
            output.put(' ');
        }
        output.put('\n');
        output.close();
    }
    return 0;
}