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

#define N 50010

typedef struct listNode{
    int val, idx;
    struct listNode *nxt;
} listNode;

typedef struct heapNode {
    int val, from, idx;
} heapNode;

int n, m, x, y, c, i;
int crtNode;
int heapPos[N], D[N], T[N];
listNode G[N];
heapNode H[N];
listNode * it;

void addEntry(int x, int y, int c) {
    listNode *aux;

    aux = malloc(sizeof(listNode));

    aux->val = c;
    aux->idx = y;
    aux->nxt = G[x].nxt;
    G[x].nxt = aux;
}

void heapSift(int idx) {
    int toSwap = 0;
    heapNode aux;
    while (idx * 2 <= H[0].val) {
        toSwap = idx * 2;
        if (idx * 2 + 1 <= H[0].val && H[idx * 2 + 1].val < H[idx * 2].val)
            toSwap = idx * 2 + 1;

        if (H[toSwap].val < H[idx].val) {
            heapPos[H[idx].idx] = toSwap;
            heapPos[H[toSwap].idx] = idx;

            aux = H[idx];
            H[idx] = H[toSwap];
            H[toSwap] = aux;

            idx = toSwap;
        } else {
            idx = N;
        }
    }
}

void heapErase(int idx) {
    H[idx] = H[H[0].val--];
    heapSift(idx);
}

void percolate(int idx) {
    heapNode aux;
    while (idx / 2 > 0 && H[idx].val < H[idx / 2].val) {
        heapPos[H[idx].idx] = idx / 2;
        heapPos[H[idx / 2].idx] = idx;

        aux = H[idx];
        H[idx] = H[idx / 2];
        H[idx / 2] = aux;

        idx /= 2;
    }
}

void heapInsert(int from, int val, int idx) {
    H[++H[0].val].from = from;
    H[H[0].val].val = val;
    H[H[0].val].idx = idx;

    heapPos[idx] = H[0].val;

    percolate(H[0].val);
}

int main()
{
    FILE *fin = fopen("dijkstra.in","r");
    FILE *fout = fopen("dijkstra.out","w");

    fscanf(fin,"%d%d",&n,&m);

    for (i = 0 ; i < m ; i++) {
        fscanf(fin,"%d%d%d",&x,&y,&c);
        addEntry(x, y, c);
        ///addEntry(y, x, c);
    }

    H[++H[0].val].idx = 1;
    H[H[0].val].val = 1;
    while (H[0].val > 0) {

        crtNode = H[1].idx;

        if (D[crtNode] != 0)
            continue;

        D[crtNode] = H[1].val;
        T[crtNode] = H[1].from;
        heapErase(1);

        for (it = G[crtNode].nxt ; it != NULL ; it = it->nxt) {
            if (D[it->idx] == 0) {

                if (heapPos[it->idx] == 0) {
                    heapInsert(crtNode, it->val + D[crtNode], it->idx);
                } else {
                    if (H[heapPos[it->idx]].val > it->val + D[crtNode]) {
                        H[heapPos[it->idx]].val = it->val + D[crtNode];
                        H[heapPos[it->idx]].from = crtNode;
                        percolate(heapPos[it->idx]);
                        heapSift(heapPos[it->idx]);
                    }
                }
            }
        }
    }

    for (i = 1 ; i <= n ; i++) {
        fprintf(fout,"%d ",D[i] - 1);
    }

    return 0;
}