#include <cstdio>
#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;
struct graf
{
    int node , cost;
};
struct pq
{
    int node2 , cost2;
    bool operator > (pq a) const
    {
        return cost2 > a . cost2;
    }
};
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 ;
                if(! mark [t . node])
                    q . pb ({t . node , dp [t . node]});
            }
        }
        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 ;
    FILE *cin , *cout;
    cin = fopen (in , "r");
    cout = fopen (out , "w");
    fscanf (cin , "%d %d" , &n , &m);
    for(i = 1 ; i <= m ; ++ i)
    {
        int a , b , c;
        fscanf (cin , "%d %d %d" , &a , &b , &c);
        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;
}