#include <stdio.h>
#define NM 50001
#define INF 10000000

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();

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 Update(int nod, int st, int dr, int pos)
{
	if ( st == dr )
	{
		a[nod] = s[st] == 1 ? 0 : st;
		return;
	}
	int mij = (st+dr)>>1;
	if ( pos <= mij ) Update(2*nod, st, mij, pos);
	if ( mij < pos ) Update(2*nod+1, mij+1, dr, pos);
	a[nod] = d[a[nod<<1]] < d[a[(nod<<1)+1]] ? a[nod<<1] : a[(nod<<1)+1];
}

void Dijkstra()
{
	for ( pos = 1; pos <= n; pos++ )
		d[pos] = (pos == 1 ? 0 : INF), Update(1, 1, n, pos);
	d[0] = INF;
    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);
    }
}