#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;

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

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, index);
    }
}

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[])
{
	
    int k = 0;
    for ( int i = 2; i <= g->nodes; ++i )
        d[i] = inf, poz[i] = -1;
    poz[1] = 1;
    h->arr[k++] = 1;
    while (k)
    {
        int min = h->arr[0];
        swap(h, 0, k - 1);
        poz[h->arr[0]] = 1;
        k--;

        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[k++] = it->node;
                    poz[h->arr[k - 1]] = k;
                    heapifyUp(h, k - 1);
                }
            }
            it = it->next;
        }    
    }
}

int main()
{
    FILE *fin = fopen("test.in", "r");
    int N, M, v1, v2, cost;
    fscanf(fin, "%d%d", &N, &M);
    graph *g = createGraph(N);
    for(int i = 1; i <= M; i++)
    {
        fscanf(fin, "%d%d%d", &v1, &v2, &cost);
        addEdge(g, v1, v2, cost);
    }
    heap *h = createHeap(N);
    
    int d[100], poz[100];
    for(int i = 1; i <= N; i++)
        d[i] = poz[i] = 0;
    dijkstra(g, h, 1, d, poz);
    for(int i = 2; i <= N; i++)
        printf("%d ", d[i]);
}