#include<stdio.h>
#include<vector>
#define INF 1<<30
#define NMAX 50100
#define MMAX 250100


struct heap
{
    int cst,nod;
} H[NMAX];

struct pair2
{
    int son,cst;
};

using namespace std;

int num,sol[NMAX];
bool used[NMAX];

vector<pair2> L[NMAX];

void pop()
{
    int son,nod = 1;
    heap aux;
    H[1] = H[num--];
    do
    {
        son = 0;
        if( 2 * nod <= num )
            {
                son = 2 * nod;
                if(2 * nod + 1 <=num && H[2 * nod + 1].cst < H[2 * nod].cst)
                    son = 2 * nod + 1;
            }
        if(H[nod].cst < H[son].cst)
            son=0;
        if(son)
            {
                aux = H[nod];
                H[nod] = H[son];
                H[son] = aux;
                nod = son;
            }
    }
    while(son);
}

void push(int node)
{
    int nod;
    heap aux;
    aux.nod = node; aux.cst = sol[node];
    H[++num] = aux; nod = num;
    while(nod / 2 > 0 && H[nod].cst < H[nod/2].cst)
    {
        aux = H[nod];
        H[nod] = H[nod / 2];
        H[nod/2] = aux;
        nod = nod / 2;
    }
}

int main()
{
    int N,M,x,now,i;
    pair2 aux;
    heap aux2;
    vector<pair2> :: iterator it;

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
        {
            scanf("%d%d%d",&x,&aux.son,&aux.cst);
            L[x].push_back(aux);
        }

    sol[1] = 0;
    for(i=2;i<=N;i++)
        sol[i] = INF;
    aux2.cst = 0; aux2.nod = 1;
    H[++num] = aux2;

    while(num)
    {
        now = H[1].nod;
        pop ();
        if( used[now])
            continue;
        used[now] = 1;
        for ( it = L[now].begin() ; it != L[now].end(); it++)
        {
            aux = *it;
            if(sol[now] + aux.cst < sol[aux.son])
                {
                    sol[aux.son] = sol[now] + aux.cst;
                    push(aux.son);
                }
        }

    }

    for(i=2;i<=N;i++)
        printf("%d ", sol[i] == INF ? 0 : sol[i]);
    return 0;
}