#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define pb push
#define pb2 push_back
using namespace std;
int const NM = 5e4 + 7 , inf = (1 << 30) + 1 , BUFF = 1e6;
struct graf
{
    int node , cost;
};
struct pq
{
    int node2 , cost2;
    bool operator > (pq a) const
    {
        return cost2 > a . cost2;
    }
};
int point;
#include <ctype.h>
char buff [BUFF];
int getbuff ()
{
    int val = 0;
    while(! isdigit (buff [point]))
    {
        ++ point;
        if(point == BUFF)
        {
            fread (buff , 1 , BUFF , stdin);
            point = 0;
        }
    }
    while(isdigit (buff [point]))
    {
        val = val * 10 + (buff [point] - '0');
        ++ point;
        if(point == BUFF)
        {
            fread (buff , 1 , BUFF , stdin);
            point = 0;
        }
    }
    return val;
}
vector <graf> v [NM];
pq heap [NM];
bitset <NM> mark;
int dp [NM] , sz;
int father (int nod)
{
    return nod / 2;
}
int left_son (int nod)
{
    return nod * 2;
}
int right_son (int nod)
{
    return nod * 2 + 1;
}
void sift (int strat)
{
    int son = 1;
    while(son)
    {
        son = 0;
        if(left_son (strat) <= sz)
        {
            son = left_son (strat);
            if(right_son (strat) <= sz && heap [son] . cost2 > heap [right_son (strat)] . cost2)
                son = right_son (strat);
            if(heap [son] . cost2 > heap [strat] . cost2)
                son = 0;
        }
        if(son)
        {
            swap (heap [son] , heap [strat]);
            strat = son;
        }
    }
}
void percolate (int strat)
{
    pq init = heap [strat];
    while((strat > 1) && init . cost2 < heap [father (strat)] . cost2)
        heap [strat] = {heap [father (strat)]} , strat = father (strat);
    heap [strat] = init;
}
void pb (int val , int val2)
{
    ++ sz;
    heap [sz] = {val , val2};
    percolate (sz);
}
void pop()
{
    heap [1] = heap [sz];
    -- sz;
    if(sz > 1 && heap [1] . cost2 < heap [father (1)] . cost2)
        percolate (1);
    else
        sift (1);
}
void bfs ()
{
    int i;
    dp [1] = 0;
    pq next = {1 , 0};
    mark [1] = 1;
    while(1)
    {
        graf t;
        for(i = 0 ; i < v [next . node2] . size () ; ++ i)
        {
            t = v [next . node2][i];
            if(dp [next . node2] + t . cost < dp [t . node])
            {
                dp [t . node] = dp [next . node2] + t . cost ;
                pb (t . node , dp [t . node]);
            }
        }
        while(sz && mark [heap [1] . node2])
            pop ();
        if(! sz)
            return;
        pq vals = heap [1];
        pop ();
        next = vals;
        mark [vals . node2] = 1;
    }
}
char const in [] = "dijkstra.in";
char const out [] = "dijkstra.out";
int main()
{
    int n , m , i ;
    freopen (in , "r" , stdin);
    fread (buff , 1 , BUFF , stdin);
    FILE *cout;
    cout = fopen (out , "w");
    n = getbuff ();
    m = getbuff ();
    for(i = 1 ; i <= m ; ++ i)
    {
        int a , b , c;
        a = getbuff ();
        b = getbuff ();
        c = getbuff ();
        v [a] . pb2 ({b , c});
    }
    for(i = 1 ; i <= n ; ++ i)
        dp [i] = inf;
    bfs ();
    for(i = 2 ; i <= n ; ++ i)
        if(dp [i] == inf)
            fprintf (cout , "0 ");
        else
            fprintf (cout , "%d " , dp [i]);
    return 0;
}