#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define maxN 50005
#define INF 0x3f3f3f3f
 
int cost[maxN] , N , M , nod;
int pozH[maxN] , H[maxN] , dim;
bool viz[maxN];
 
vector < pair <int , int> > lista[maxN];
 
void push (int nod)
{
    int tata = nod / 2;
     
    if (nod == 1)
        return ;
     
    if (cost[H[tata]] <= cost[H[nod]])
        return;
     
    swap (H[nod] , H[tata]);
    swap (pozH[H[nod]] , pozH[H[tata]]);
     
    push (pozH[H[tata]]);
}
 
 
void pop (int nod)
{
    int f1 , f2 , nodmin = nod;
     
    f1 = nod * 2;
    f2 = nod * 2 + 1;
     
    if (f1 <= dim && cost[H[f1]] < cost[H[nodmin]])
        nodmin = f1;
     
    if (f2 <= dim && cost[H[f2]] < cost[H[nodmin]])
        nodmin = f2;
     
    if (nod == nodmin)
        return;
     
    swap (H[nodmin] , H[nod]);
    swap (pozH[H[nodmin]] , pozH[H[nod]]);
     
    pop (pozH[H[nodmin]]);
 
}
 
 
void get_min ()
{
    nod = H[1];
     
    viz[nod] = true;
     
    swap (H[1] , H[dim]);
    swap (pozH[H[1]] , pozH[H[dim]]);
     
    --dim;
     
    pop (pozH[H[1]]);
}
 
 
int main ()
{
    freopen ("dijkstra.in" , "r" , stdin);
    freopen ("dijkstra.out" , "w" , stdout);
     
    scanf ("%d %d" , &N , &M);
     
    for (int i = 1 ; i <= N ; ++i)
        cost[i] = INF;
     
    cost[1] = 0;
     
    for (int i = 1 ; i <= N ; ++i)
    {
        pozH[i] = ++dim;
        H[dim] = i;
         
        push (pozH[i]);
    }
     
    int a , b , c;
     
    for (int i = 1 ; i <= M ; ++i)
    {
        scanf ("%d %d %d" , &a , &b , &c);
         
        lista[a]. push_back (make_pair (b , c));
    }
     
    int nodcur , costmuc;
     
    for (int t = 1 ; t <= N ; ++t)
    {
        get_min ();
         
        for (unsigned i = 0 ; i < lista[nod].size () ; ++i)
        {
            nodcur = lista[nod][i].first;
            costmuc = lista[nod][i].second;
             
            if (viz[nodcur]) continue;
             
            if (cost[nod] + costmuc < cost[nodcur])
            {
                cost[nodcur] = cost[nod] + costmuc;
                 
                push (pozH[nodcur]);
            }
        }
    }
     
    for (int i = 2 ; i <= N ; ++i)
    {
        if (cost[i] == INF)
        {
            printf ("0 ");
            continue;
        }
         
        printf ("%d " , cost[i]);
    }
     
    return 0;
}