#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];
priority_queue <pq , vector <pq> , greater <pq> > q;
bitset <NM> mark;
int dp [NM];
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 ;
                q . pb ({t . node , dp [t . node]});
            }
        }
        while(! q . empty () && mark [q . top () . node2])
            q . pop ();
        if(q . empty ())
            return;
        pq vals = q . top ();
        q . 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;
}