#include <stdio.h>
#include <stdlib.h>

#define Vmax 50001
#define INT_MAX 2147483647

typedef struct VectorNode {
    int to_node;
    int cost;
    struct VectorNode* next;
} VectorNode;

typedef struct {
    int cost;
    int node_id;
} HeapNode;

typedef struct {
    HeapNode* items;
    int size;
    int capacity;
} PriorityQueue;

inline void verify_allocation(void* ptr)
{
    if (ptr == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
}

inline void siftUp(PriorityQueue* pq, int index)
{
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (pq->items[parent].cost <= pq->items[index].cost) {
            break;
        }
        HeapNode temp = pq->items[parent];
        pq->items[parent] = pq->items[index];
        pq->items[index] = temp;
        index = parent;
    }
}

inline void siftDown(PriorityQueue* pq, int index)
{
    while (2 * index + 1 < pq->size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = left;

        if (right < pq->size && pq->items[right].cost < pq->items[left].cost) {
            smallest = right;
        }
        if (pq->items[index].cost <= pq->items[smallest].cost) {
            break;
        }
        HeapNode temp = pq->items[index];
        pq->items[index] = pq->items[smallest];
        pq->items[smallest] = temp;
        index = smallest;
    }
}

PriorityQueue* createPQ(int capacity)
{
    PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    if (pq == NULL) {
        fprintf(stderr, "Memory allocation failed for priority queue\n");
        exit(1);
    }
    pq->items = (HeapNode*)malloc(capacity * sizeof(HeapNode));
    if (pq->items == NULL) {
        fprintf(stderr, "Memory allocation failed for priority queue items\n");
        free(pq);
        exit(1);
    }
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void freePQ(PriorityQueue* pq)
{
    if (pq != NULL) {
        free(pq->items);
        free(pq);
    }
}

int isEmpty(PriorityQueue* pq)
{
    return pq->size == 0;
}

void push(PriorityQueue* pq, int cost, int node_id)
{
    if (pq->size >= pq->capacity) {
        pq->capacity *= 2;
        pq->items = realloc(pq->items, pq->capacity * sizeof(HeapNode));
        if (pq->items == NULL) {
            fprintf(stderr, "Memory allocation failed when resizing priority queue\n");
            exit(1);
        }
    }
    pq->items[pq->size].cost = cost;
    pq->items[pq->size].node_id = node_id;
    pq->size++;
    siftUp(pq, pq->size - 1);
}

inline HeapNode pop(PriorityQueue* pq)
{
    if (pq->size == 0) {
        fprintf(stderr, "Pop from empty priority queue\n");
        exit(1);
    }
    HeapNode root = pq->items[0];
    pq->items[0] = pq->items[pq->size - 1];
    pq->size--;

    siftDown(pq, 0);
    return root;
}

void addEdge(VectorNode** head_ptr, int to_node, int cost) {
    VectorNode* newNode = (VectorNode*)malloc(sizeof(VectorNode));
    verify_allocation(newNode);

    newNode->to_node = to_node;
    newNode->cost = cost;

    newNode->next = *head_ptr;

    *head_ptr = newNode;
}

void freeGraph(VectorNode** adj, int n_nodes) {
    for (int i = 1; i <= n_nodes; i++) {
        VectorNode* current = adj[i];
        while (current != NULL) {
            VectorNode* toDelete = current;
            current = current->next;
            free(toDelete);
        }
    }
    free(adj);
}

int dist[Vmax];
int current_size = 0;


void open_files(FILE** fin, FILE** fout)
{
    *fin = fopen("dijkstra.in", "r");
    *fout = fopen("dijkstra.out", "w");
    if (*fin == NULL) {
        printf("Error: Could not open dijkstra.in\n");
        exit(1); 
    }
    if (*fout == NULL) {
        printf("Error: Could not open dijkstra.out\n");
        exit(1);
    }
}

void close_files(FILE** fin, FILE** fout)
{
    if (*fin != NULL) {
        fclose(*fin);
    }
    if (*fout != NULL) {
        fclose(*fout);
    }
}

void bfs(VectorNode** v, int m)
{
    dist[1] = 0;
    PriorityQueue* pq = createPQ(m + 1);
    push(pq, 0, 1);
    while (!isEmpty(pq)) {
        HeapNode current = pop(pq);
        int vec = current.node_id;
        int distanta_vec = -current.cost;
        if (distanta_vec > dist[vec])
            continue;
        VectorNode* neighbour = v[vec];
        while(neighbour != NULL) {
            int cost = neighbour->cost;
            int to_node = neighbour->to_node;
            if (dist[to_node] > dist[vec] + cost) {
                dist[to_node] = dist[vec] + cost;
                push(pq, -dist[to_node], to_node);
            }
            neighbour = neighbour->next;
        }
    }
    freePQ(pq);
}

int main()
{
    FILE *fin = NULL, *fout = NULL;
    open_files(&fin, &fout);
    int n, m;
    fscanf(fin, "%d %d", &n, &m);
    VectorNode** v = (VectorNode**)calloc(5 * Vmax, sizeof(VectorNode*));
    verify_allocation(v);
    

    for(int i = 0; i <= n; i++) {
        dist[i] = INT_MAX;
    }
    for(int i = 1; i <= m; i++) {
        int x, y, z;
        fscanf(fin, "%d %d %d", &x, &y, &z);
        addEdge(&v[x], y, z);
    }
    bfs(v, n);
    for(int i = 2; i <= n; i++) {
        if(dist[i] == INT_MAX) 
            fprintf(fout, "0 ");
        else 
            fprintf(fout, "%d ", dist[i]);
    }
    
    freeGraph(v, m);
    close_files(&fin, &fout);
    return 0;
}