#include <stdio.h>   
#include <string.h>   
  
#define MAXN 50001   
#define INF 0x3f3f3f3f   
  
int *lv[MAXN], *cost[MAXN];   
int N, M;   
int H[MAXN], hsz;   
int ind[MAXN];   
int gr[MAXN];   
int dist[MAXN];   
int a, b, c;   
char s[1<<7];   
  
void get ()   
{   
    gets (s);   
  
    int i, ten;       
    a=b=c=0;   
    for (i = strlen(s) - 1, ten = 1; s[i] != ' '; --i, ten *= 10)   
        c += (s[i] - '0') * ten;   
    for (--i, ten = 1; s[i] != ' '; --i, ten *= 10)   
        b += (s[i] - '0') * ten;   
    for (--i, ten = 1; i >= 0; --i, ten *= 10)   
        a += (s[i] - '0') * ten;   
}   
  
void read ()   
{   
    int i;   
  
    scanf ("%d %d\n", &N, &M);   
    for (i = 0; i < M; ++ i)   
    {   
        get ();   
        //printf ("%d %d %d\n", a, b, c);   
        ++gr[a];   
    }   
  
    for (i = 1; i <= N; ++ i)   
    {   
        lv[i] = new int [gr[i] + 1];   
        cost[i] = new int [gr[i] + 1];   
        lv[i][0] = 0;   
    }   
  
    fseek (stdin, 0, SEEK_SET);   
  
    scanf ("%d %d\n", &N, &M);   
    for (i = 0; i < M; ++ i)   
    {   
        get ();   
        lv[a][++lv[a][0]] = b;   
        cost[a][lv[a][0]] = c;   
    }   
       
    /*for (i = 1; i <= N; ++ i)  
    {  
       for (int j = 1; j <= lv[i][0]; ++ j)  
           printf ("%d ", lv[i][j]);  
        printf ("\n");  
    }*/  
}   
  
void update (int x)   
{   
    int tata, fiu, val;   
    val = H[x];   
    fiu = x;   
    tata = fiu / 2;   
  
    while (tata > 0)   
    {   
        if (dist[val] > dist[H[tata]]) break;   
  
        H[fiu] = H[tata];   
        ind[H[fiu]] = fiu;   
  
        fiu = tata;   
        tata = fiu / 2;   
    }   
  
    H[fiu] = val;   
    ind[H[fiu]] = fiu;   
}   
  
void combheap (int x)   
{   
    int tata, fiu, val;   
    val = H[x];   
    tata = x;   
    fiu = 2*x;   
  
    while (fiu <= hsz)   
    {   
        if (fiu < hsz)   
            if (dist[H[fiu]] > dist[H[fiu+1]]) ++fiu;   
  
        if (dist[val] < dist[H[fiu]]) break;   
  
        H[tata] = H[fiu];   
        ind[H[tata]] = tata;   
  
        tata = fiu;   
        fiu = 2*tata;   
    }   
  
    H[tata] = val;   
    ind[H[tata]] = tata;   
}   
  
void dijkstra (int s)   
{   
    int i, j;   
    memset (dist, INF, sizeof(dist));   
    dist[s] = 0;   
  
    hsz = N;   
    for (i = 1; i <= N; ++ i)   
    {   
        H[i] = i;   
        ind[i] = i;   
    }   
  
    for (i = hsz / 2; i > 0; -- i)   
        combheap (i);   
  
    int nod;   
    for (i = 1; i <= N; ++ i)   
    {   
        nod = H[1];   
        H[1] = H[hsz--];   
        combheap (1);   
  
        for (j = 1; j <= lv[nod][0]; ++ j)   
            if (dist[nod] + cost[nod][j] < dist[lv[nod][j]])   
            {   
                dist[lv[nod][j]] = dist[nod] + cost[nod][j];   
                update (ind[lv[nod][j]]);   
            }   
    }   
}   
  
void solve ()   
{   
    dijkstra (1);   
  
    int i;   
    for (i = 2; i <= N; ++ i)   
        printf ("%d ", dist[i] >= INF ? 0 : dist[i]);   
    printf ("\n");   
}   
  
int  
 main ()   
{   
    freopen ("dijkstra.in", "rt", stdin);   
    freopen ("dijkstra.out", "wt", stdout);   
  
    read ();   
    solve ();   
  
    return 0;   
}