#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXN 50001
#define INF 0x3f3f3f3f

int *lv[MAXN], *cost[MAXN];
int N, M, hsz;
int H[MAXN];
int dist[MAXN];
int ind[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 = 1; i <= N; ++ i)
	{
        lv[i] = (int *) realloc (lv[i], sizeof (int));
        cost[i] = (int *) realloc (cost[i], sizeof (int));
        lv[i][0] = 0;
    }   
	for (i = 0; i < M; ++ i)
	{
        get ();
        ++lv[a][0];
        lv[a] = (int *) realloc (lv[a], (lv[a][0] + 1) * sizeof (int));
        cost[a] = (int *) realloc (cost[a], (lv[a][0] + 1) * sizeof (int));
        cost[a][lv[a][0]] = c;
        lv[a][lv[a][0]] = b;
	}
}

void combheap (int a)
{
    int fiu, tata, val;
    
    val = H[a];
    tata = a;
    fiu = a * 2;
    
    while (fiu <= hsz)
    {
        if (fiu < hsz)
            if (dist[H[fiu+1]] < dist[H[fiu]]) ++fiu;
            
        if (dist[val] < dist[H[fiu]]) break;
        
        H[tata] = H[fiu];
        ind[H[tata]] = tata;
        
        tata = fiu;
        fiu = tata * 2;                
    }
    
    H[tata] = val;
    ind[H[tata]] = tata;
}

void update (int a)
{
    int fiu, tata, val;
    
    val = H[a];
    fiu = a;
    tata = a / 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 dijkstra (int s)
{
    int i, j, nod;
    
    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);
        
    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[lv[nod][j]] > dist[nod] + cost[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;
}