#include <stdio.h>
#include <stdlib.h>
#define inf 9999999

typedef struct listNode{
    // Nodul cu care are muchie detinatorul listei 
    int node;
    // Costul dintre detinatorul listei si node
    int cost;
    struct listNode *next;
} listNode;

typedef struct graph{
    // Numarul de noduri ale grafului
    int nodes;
    // adj_heads[i] -> lista de adiacenta a nodului i 
    listNode **adj_heads;
} graph;

typedef struct heap{
    int *arr;
    int size;
}heap;

heap *createHeap(int n)
{
    heap *new = malloc(sizeof(heap));
    new->arr = calloc(n, sizeof(int));
    new->size = 0;
}

int getLeftChild(int index)
{
    return 2 * index + 1;
}

int getRightChild(int index)
{
    return 2 * index + 2;
}

int getParent(int index)
{
    return (index - 1) / 2;
}

void swap(heap *h, int i, int j)
{
    int temp = h->arr[i];
    h->arr[i] = h->arr[j];
    h->arr[j] = temp;
}

int hasLeftChild(heap *h, int index)
{
    return getLeftChild(index) < h->size;
}

int hasRightChild(heap *h, int index)
{
    return getRightChild(index) < h->size;
}

void heapifyUp(heap *h, int index)
{
    if(index)
    {
        int parent = getParent(index);
        if(h->arr[parent] < h->arr[index])
        {
            swap(h, parent, index);
            heapifyUp(h, parent);
        }
    }
}

void insert(heap *h, int x)
{
    h->arr[h->size] = x;
    heapifyUp(h, h->size);
    h->size++; 
}

void heapifyDown(heap *h, int index)
{
    int leftChild = getLeftChild(index);
    int rightChild = getRightChild(index);

    int max = index;
    if(hasLeftChild(h, index) && h->arr[leftChild] > h->arr[max]) max = leftChild;
    if(hasRightChild(h, index) && h->arr[rightChild] > h->arr[max]) max = rightChild;

    if(max != index)
    {
        swap(h, max, index);
        heapifyDown(h, max);
    }
}

void addEdge(graph *g, int v1, int v2, int cost)
{
    listNode *new;
    new = (listNode *) malloc(sizeof(listNode));
    new->node = v2;
    new->cost = cost;
    new->next = g->adj_heads[v1];
    g->adj_heads[v1] = new;
}

void removeEdge(graph *gl, int v1, int v2)
{
    listNode *prev, *cur;
    cur = gl->adj_heads[v1];
    
    if(cur->node == v2)
    {
        listNode *aux = cur;
        cur = cur->next;
        gl->adj_heads[v1] = cur;
        free(aux);
    }
    
    while(cur)
    {
        if(cur->node == v2) break;
        prev = cur;
        cur = cur->next;
    }
    
    if(!cur) return;

    if(cur->next == NULL)
    {
        prev->next = NULL;
        free(cur);
        return;
    }
    
    prev->next = cur->next;
    free(cur);
}

graph *createGraph(int nodes)
{
    graph *g = (graph*) malloc(sizeof(graph));

    g->nodes = nodes;
    g->adj_heads = (listNode**) calloc(nodes + 1, sizeof(listNode*));

    return g;
}

void dijkstra(graph *g, heap *h, int source, int d[], int poz[])
{
    
    for ( int i = 1; i <= g->nodes; ++i )
        if(i != source) d[i] = inf, poz[i] = -1;
    
    poz[source] = 1;
    h->arr[h->size++] = source;
    while(h->size)
    {
        int min = h->arr[0];
        swap(h, 0, h->size - 1);
        poz[h->arr[0]] = 1;
        h->size--;

        heapifyDown(h, 0);

        listNode *it = g->adj_heads[min];
        while (it)
        {
            if (d[it->node] > d[min] + it->cost)
            {
                d[it->node] = d[min] + it->cost;
                if (poz[it->node] != -1)
                    heapifyUp(h, poz[it->node] - 1); 
                else
                {
                    h->arr[h->size++] = it->node;
                    poz[h->arr[h->size - 1]] = h->size;
                    heapifyUp(h, h->size - 1);
                }
            }
            it = it->next;
        }    
    }
}

int main()
{
    graph *g;
    heap *h;
    FILE *fin = fopen("dijkstra.in", "r");
    FILE *fout = fopen("dijkstra.out", "w");
    int N, M, v1, v2, cost, d[10000], q[10000], min, X, rep[1000], ans;
    
    fscanf(fin, "%d%d", &N, &M);
    g = createGraph(N);
    h = createHeap(N);

    for(int i = 1; i <= M; i++)
    {
        fscanf(fin, "%d%d%d", &v1, &v2, &cost);
        addEdge(g, v1, v2, cost);
    }

    for(int i = 1; i <= N; i++)
        frpintf(fout, "%d ", d[i] == inf ? 0 : d[i]);
    fprintf(fout, "\n");
    
    return 0;
}