#include <fstream>
#include <vector>
#include <ctype.h>
#include <queue>
#include <bitset>
#define inf INFINIT
using namespace std;
char const in [] = "dijkstra.in";
char const out [] = "dijkstra.out";
struct graf
{
    int node , cost;
};
int const NM = 50007 , NM2 = 1000000 , INFINIT = (1 << 30) , NMAX = 250007;
int n;
char buff [NM2];
graf heap [NMAX];
int point , sol [NM];
vector <graf> v [NMAX];
queue <int> q;
bitset <NM> mark;
int dp [NM];
int getbuff ()
{
    while(! isdigit (buff [point]))
    {
        if(point == NM2 )
        {
            point = 0;
            fread(buff , 1 , NM2 , stdin );
        }
        ++ point;
    }
    int val = 0;
    while(isdigit (buff [point]))
    {
        val = val * 10 + (buff [point] - '0');
        if(point == NM2)
        {
            point = 0;
            fread(buff , 1 , NM2 , stdin );
        }
        ++ point;
    }
    return val;
}
int father (int nod)
{
    return nod / 2;
}
int left_son (int nod)
{
    return nod * 2;
}
int right_son (int nod)
{
    return nod * 2 + 1;
}
int sz , t;
void sift (int strat)
{
    int son = 1;
    while(son)
    {
        son = 0;
        if(left_son (strat) <= sz)
        {
            son = left_son (strat);
            if(right_son (strat) <= n && heap [right_son (strat)] . cost  < heap [son] . cost)
                son = right_son (strat);
            if(heap [strat] . cost< heap [son] . cost)
                son = 0;
        }
        if(son)
        {
            swap (heap [strat] , heap [son]);
            strat = son;
        }
    }
}
void build_heap (int sz)
{
    for(int i = n / 2 ; i > 0 ; -- i)
        sift(i);
}
void percolate (int pos)
{
    graf key = heap [pos];
    while(pos > 1 && key . cost < heap [father (pos)] . cost )
    {
        heap [pos] = heap [father (pos)];
        pos = father (pos);
    }
    heap [pos] = key;
}
void heap_pop (int pos)
{
    heap [pos] = heap [sz];
    -- sz;
    if((pos > 1) && heap [pos] . cost < heap [father (pos)] . cost )
        percolate (pos);
    else
        sift (pos);
}
int position (int nod)
{
    int i;
    for(i = 1 ; i <= n ; ++ i)
        if(heap [i] . node == nod)
            return i;
}
void bfs ()
{
    q . push (1);
    mark [1] = 1;
    dp [1] = 0;
    sz = t + 1;
    int i;
    int atpos = 1;
    while(sz)
    {
        build_heap (sz);
        graf minval = heap [1];
        if(! sol [minval . node])
            sol [minval . node] = minval . cost;
        heap_pop (1);
        int poz = minval . node ;
        for(i = 0 ; i < v [poz] . size () ; ++ i )
        {
            graf value = v [poz][i];
            if(heap [value . node] . cost >= minval . cost + v [poz][i] . cost )
                    heap [position (value . node)] . cost = minval . cost + v [poz][i] . cost;
        }
        ++ atpos;
    }
}
int main()
{
    int i , point_ = 1;
    freopen (in , "r" , stdin);
    freopen (out , "w" , stdout);
    fread (buff , 1 , NM2 , stdin);
    n = getbuff ();
    t = getbuff ();
    heap [point_] = {1 , 0};
    for(i = 1 ; i <= t ; ++ i)
    {
        int a , b , c;
        a = getbuff ();
        b = getbuff ();
        c = getbuff ();
        v [a] . push_back ({b , c});
        heap [++ point_] = {b , inf};
    }
    bfs ();
    for(i = 2 ; i <= n ; ++ i)
        printf ("%d " , sol [i] );
    return 0;
}