#include <cstdio>
#include <queue>
#include <vector>
#include <bitset>
#define inf (1 << 30)
using namespace std;
struct code
{
    int node , cost;
};
struct pqueue
{
    int nod , val;
    bool operator > (pqueue a) const
    {
        return val < a . val;
    }
};
vector <code> v [50007];
int sol [50007];
priority_queue <pqueue , vector <pqueue> , greater <pqueue> > pq;
bitset <50007> mark;
void bfs ()
{
    int last = 1 , i;
    mark [1] = 1;
    while(1)
    {
        for(i = 0 ; i < v [last] .size () ; ++ i)
        {
            code a = v [last][i];
            if(sol [a . node] > sol [last] + a . cost)
            {
                sol [a . node] = sol [last] + a . cost;
                pq . push ({a . node , sol [a . node]});
            }
        }
        while(! pq . empty () && mark [pq . top () . nod])
            pq . pop ();
        if(pq . empty ())
            return;
        int next = pq . top () . nod;
        pq . pop ();
        last = next;
        mark [last] = 1;
    }
}
int main()
{
    int n , m , i ,a , b , c;
    FILE *cin , *cout;
    cin = fopen ("dijkstra.in" , "r");
    cout = fopen ("dijkstra.out" , "w");
    fscanf (cin , "%d %d" , &n , &m);
    for(i = 1 ; i <= m ; ++ i)
    {
        fscanf (cin , "%d %d %d" , &a , &b , &c);
        v [a] . push_back ({b , c});
    }
    for(i = 2 ; i <= n ; ++ i)
        sol [i] = inf;
    bfs ();
    for(i = 2 ; i <= n ; ++ i)
        if(sol [i] == inf)
            fprintf (cout , "0 ");
        else
            fprintf(cout , "%d " , sol [i]);
    return 0;
}