#include <fstream>

struct data
{
    unsigned int number;
    unsigned int distance;
};

struct list
{
    struct data vertex;
    struct list *next;
};

struct linked_list
{
    struct list *head;
};

std::ofstream debug("d.out");

inline void heap_up (unsigned int *heap, unsigned int *heap_index, unsigned int *shortest_path, unsigned int index)
{
    unsigned int vertex(heap[index]), distance(shortest_path[vertex]), father((index - 1) >> 1), vertex_father(heap[father]);
    while (distance < shortest_path[vertex_father])
    {
        heap_index[vertex] ^= heap_index[vertex_father];
        heap_index[vertex_father] ^= heap_index[vertex];
        heap_index[vertex] ^= heap_index[vertex_father];
        heap[index] = heap[father];
        index = father;
        if (father)
        {
            --father;
            father >>= 1;
            vertex_father = heap[father];
        }
        else
            break;
    }
    heap[index] = vertex;
}

inline void heap_down (unsigned int *heap, unsigned int *heap_index, unsigned int *shortest_path, unsigned int index, unsigned int size)
{
    unsigned int left((index << 1) + 1), right(left + 1), smallest, vertex, smallest_vertex;
    while (true)
    {
        if (left < size && shortest_path[heap[left]] < shortest_path[heap[index]])
            smallest = left;
        else
            smallest = index;
        if (right < size && shortest_path[heap[right]] < shortest_path[heap[smallest]])
            smallest = right;
        if (smallest == index)
            break;
        vertex = heap[index];
        smallest_vertex = heap[smallest];
        heap_index[vertex] ^= heap_index[smallest_vertex];
        heap_index[smallest_vertex] ^= heap_index[vertex];
        heap_index[vertex] ^= heap_index[smallest_vertex];
        heap[index] ^= heap[smallest];
        heap[smallest] ^= heap[index];
        heap[index] ^= heap[smallest];
        index = smallest;
        left = (index << 1) + 1;
        right = left + 1;
    }
}

inline void pop (unsigned int *heap, unsigned int *heap_index, unsigned int *shortest_path, unsigned int &size)
{
    --size;
    *heap = heap[size];
    heap_index[*heap] = 0;
    heap_down(heap,heap_index,shortest_path,0,size);
}

inline void Dijkstra (struct linked_list *graph, unsigned int *shortest_path, unsigned int n)
{
    unsigned int *heap_index(new unsigned int [n]);
    unsigned int *heap(new unsigned int [n]);
    for (unsigned int i(0) ; i < n ; ++i)
    {
        shortest_path[i] = -1;
        heap_index[i] = heap[i] = i;
    }
    *shortest_path = 0;
    unsigned int min_vertex, vertex, min_path, new_path;
    struct list *iterator;
    do
    {
        min_vertex = *heap;
        min_path = shortest_path[min_vertex];
        pop(heap,heap_index,shortest_path,n);
        if (min_path == -1)
            goto Skip;
        iterator = graph[min_vertex].head;
        while (iterator)
        {
            new_path = min_path + iterator->vertex.distance;
            vertex = iterator->vertex.number;
            if (new_path < shortest_path[vertex])
            {
                shortest_path[vertex] = new_path;
                vertex = heap_index[vertex];
                if (vertex && shortest_path[heap[vertex]] < shortest_path[heap[(vertex - 1) >> 1]])
                    heap_up(heap,heap_index,shortest_path,vertex);
            }
            iterator = iterator->next;
        }
        Skip : ;
    }
    while (n);
}

int main (void)
{
    std::ifstream input("dijkstra.in");
    unsigned int n,m;
    input >> n >> m;
    struct linked_list *graph(new struct linked_list [n] ( ));
    {
        unsigned int node1, node2, path;
        struct list *new_element;
        do
        {
            input >> node1 >> node2 >> path;
            --m;
            --node1;
            --node2;
            new_element = new struct list;
            new_element->vertex.number = node2;
            new_element->vertex.distance = path;
            new_element->next = graph[node1].head;
            graph[node1].head = new_element;
        }
        while (m);
    }
    input.close();
    unsigned int *shortest_path(new unsigned int [n]);
    Dijkstra(graph,shortest_path,n);
    {
        unsigned int *iterator(shortest_path + 1);
        const unsigned int *const END(shortest_path + n);
        std::ofstream output("dijkstra.out");
        while (true)
        {
            if (*iterator == -1 || !*iterator)
                output.put('0');
            else
                output << *iterator;
            ++iterator;
            if (iterator == END)
                break;
            output.put(' ');
        }
        output.put('\n');
        output.close();
    }
    return 0;
}