#include <stdio.h>
#define NM 50001
#define INF 10000000
#define lf (nod<<1)
#define rt (lf+1)
#define mij ((st+dr)>>1)

int n, m, a[3*NM];
int i, j, k, pos, d[NM], s[NM];
typedef struct nod {
    int vf, c;
    nod* urm;
} NOD, *PNOD;
PNOD l[NM];
    
void Update(int nod, int st, int dr);
void Add(int i, int j, int k);
void Dijkstra();
void Build(int nod, int st, int dr);

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for ( pos = 1; pos <= m; pos++ )
        scanf("%d %d %d", &i, &j, &k),
        Add(i, j, k);
    Dijkstra();
    for ( i = 2; i <= n; i++ )
        printf("%d ", d[i] == INF ? 0 : d[i]);
    printf("\n");
    
    return 0;
}

void Add(int i, int j, int k)
{
    PNOD q = new NOD;
    q->vf = j;
    q->c = k;
    q->urm = l[i];
    l[i] = q;
}

void Build(int nod, int st, int dr)
{
    if ( st == dr ) 
    {
        a[nod] = st;
        return;
    }
    Build(lf, st, mij);
    Build(rt, mij+1, dr);
    a[nod] = d[a[lf]] < d[a[rt]] ? a[lf] : a[rt];
}
    
void Update(int nod, int st, int dr, int pos)
{
	if ( st == dr )
	{
		a[nod] = s[st] == 1 ? 0 : st;
		return;
	}
	if ( pos <= mij ) Update(lf, st, mij, pos);
	if ( mij < pos ) Update(rt, mij+1, dr, pos);
	a[nod] = d[a[lf]] < d[a[rt]] ? a[lf] : a[rt];
}

void Dijkstra()
{
	for ( pos = 0; pos <= n; pos++ )
		d[pos] = (pos == 1 ? 0 : INF);
	Build(1, 1, n);
    for ( int h = 1; h <= n; h++ )
    {
        k = a[1]; s[k] = 1; 
        for ( PNOD q = l[k]; q; q = q->urm )
            if ( !s[q->vf] && d[q->vf] > d[k] + q->c )
            {
                d[q->vf] = d[k] + q->c;
                Update(1, 1, n, q->vf);
            }
		Update(1, 1, n, k);
    }
}