#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>

typedef long long i64;
#define UNUSED -1
#define inf 1000000000
#define N_MAX 300000
#define M_MAX 300000
#define K_MAX 300000
const i64 INF = 1e18;

void swap(void *a, void* b, size_t size)
{
    uint8_t aux[size];
    memcpy(aux, a, size);
    memcpy(a, b, size);
    memcpy(b, aux, size);
}
//////////////////////////////////
typedef struct {
    int from, to, dist;
    i64 final_distance;
} edge;
int n, m, k, source, destination;
int **adj, *adj_size;
edge *edges;
/////////////////////////////////
//////////step 1/////////////////
//We are doing the first dijkstra from the destination node
typedef struct {
    i64 value;
    int index;
} heap_node_1;

//verifys if the first is better then the second
bool better(heap_node_1 a, heap_node_1 b)
{
    return a.value <= b.value;
}
int heap_1_sz = 0;
heap_node_1 *heap_1;
i64 *dist_init;
int *best_edge;
int left_child(int x)
{
    return 2 * x;
}

int right_child(int x)
{
    return 2 * x + 1;
}

int parent(int x)
{
    return x / 2;
}

void push_up_1(int poz)
{
    while (poz > 1 && better(heap_1[poz], heap_1[parent(poz)]))
    {
        swap(&heap_1[poz], &heap_1[parent(poz)], sizeof(heap_node_1));
        poz = parent(poz);
    }
}
void push_down_1(int poz)
{
    while (right_child(poz) <= heap_1_sz && (better(heap_1[left_child(poz)], heap_1[poz]) ||
                                             better(heap_1[right_child(poz)], heap_1[poz])))
    {
        if (better(heap_1[left_child(poz)], heap_1[right_child(poz)]))
        {
            swap(&heap_1[poz], &heap_1[left_child(poz)], sizeof(heap_node_1));
            poz = left_child(poz);
        }
        else
        {
            swap(&heap_1[poz], &heap_1[right_child(poz)], sizeof(heap_node_1));
            poz = right_child(poz);
        }
    }
    if (left_child(poz) <= heap_1_sz && better(heap_1[left_child(poz)], heap_1[poz]))
    {
        swap(&heap_1[poz], &heap_1[left_child(poz)], sizeof(heap_node_1));
    }
}

void heap_1_add(i64 val, int index)
{
    heap_1_sz++;
    heap_1[heap_1_sz].value = val;
    heap_1[heap_1_sz].index = index;
    push_up_1(heap_1_sz);
}

heap_node_1 heap_1_min()
{
    assert(heap_1_sz > 0);
    return heap_1[1];
}

void heap_1_pop()
{
    heap_1[1] = heap_1[heap_1_sz];
    heap_1_sz--;
    push_down_1(1);
}

void dijkstra()
{
    for (int i = 0; i < n; i ++)
    {
        dist_init[i] = INF;
        best_edge[i] = UNUSED;
    }
    dist_init[destination] = 0;
    heap_1_add(0, destination);
    while (heap_1_sz > 0)
    {
        int from = heap_1_min().index;
        i64 dist_from = heap_1_min().value;
        heap_1_pop();
        if (dist_init[from] != dist_from)
        {
            continue;
        }
        for (int i = 0; i < adj_size[from]; i++)
        {
            int ind_edge = adj[from][i];
            int to = edges[ind_edge].to;
            int weight = edges[ind_edge].dist;
            if (dist_init[to] > dist_from + weight)
            {
                dist_init[to] = dist_from + weight;
                best_edge[to] = ind_edge;
                heap_1_add(dist_init[to], to);
            }
        }
    }
    for (int i = 1; i < n; i++)
    {
        printf("%lld ", dist_init[i]);
    }
}
/////////////////////////////////////
///
///
void read_graph()
{
    edges = (edge *) malloc(m * sizeof(edge));
    adj = (int **) malloc(n * sizeof(int *));
    adj_size = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &edges[i].from, &edges[i].to, &edges[i].dist);
        edges[i].from--;
        edges[i].to--;
        adj_size[edges[i].from]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (adj_size[i] > 0)
        {
            adj[i] = (int *)malloc(adj_size[i] * sizeof(int));
            adj_size[i] = 0;
        }
    }
    for (int i = 0; i < m; i++)
    {
        int from = edges[i].from;
        adj[from][adj_size[from]++] = i;
    }
}

void read_data()
{
    // scanf("%d%d%d%d%d", &n, &m, &source, &destination, &k);
    scanf("%d%d", &n, &m);
    // printf("x%dx", n);
    destination = 1;
    source--;
    destination--;
    heap_1 = (heap_node_1 *) malloc((n + 1) * sizeof(heap_node_1));
    best_edge = (int *) malloc(n * sizeof(int));
    dist_init = (i64 *) malloc(n * sizeof(i64));
    read_graph();
}

void free_data()
{
    for (int i = 0; i < n; i++)
    {
        if (adj_size[i] > 0)
        {
            free(adj[i]);
        }
    }
    free(adj);
    free(adj_size);
    free(edges);
    free(heap_1);
    free(best_edge);
    free(dist_init);
}

int main(void)
{
    // setbuf(stdout, NULL);
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    read_data();
    dijkstra();
    free_data();
    return 0;
}