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

typedef struct		s_list
{
	struct s_list	*next;
	int				cost;
	int				node;
}					t_list;

typedef	struct		s_queue
{
	struct s_queue	*next;
	int				value;
}					t_queue;

int		n, m;
t_list	*v[50000];
int		viz[50000];
int		cost[50000];
t_queue	*begin, *end;

t_queue	*ft_create_queue(int nod)
{
	t_queue	*new;

	new = (t_queue*)malloc(sizeof(t_queue));
	new->next = NULL;
	new->value = nod;
	return (new);
}

t_list	*ft_create_elem(int nod, int cost)
{
	t_list	*new;

	new = (t_list*)malloc(sizeof(t_list));
	new->next = NULL;
	new->cost = cost;
	new->node = nod;
	return (new);
}

void	ft_insert_elem(t_list **begin_list, int nod, int cost)
{
	t_list	*list;
	t_list	*new;
	int		ok;

	if (!(*begin_list))
		*begin_list = ft_create_elem(nod, cost);
	else
	{
		list = *begin_list;
		ok = 1;
		if (nod < list->node)
		{
			new = ft_create_elem(nod, cost);
			new->next = list;
			*begin_list = new;
		}
		else
			while (list && ok)
			{
				if (list->next == NULL)
				{
					new = ft_create_elem(nod, cost);
					list->next = new;
					ok = 0;
				}
				else if (nod < list->next->node)
				{
					new = ft_create_elem(nod, cost);
					new->next = list->next;
					list->next = new;
					ok = 0;
				}
				list = list->next;
			}
	}
}

void	ft_print_list(t_list *begin_list)
{
	t_list	*list;

	list = begin_list;
	while (list)
	{
		printf("%d,%d   ", list->node, list->cost);
		list = list->next;
	}
}

void	ft_test_print(void)
{
	int		i;

	for (i = 1; i <= n; i++)
	{
		printf("%d: ", i);
		ft_print_list(v[i]);
		printf("\n");
	}
}

int		minim(int a, int b)
{
	if (a < b)
		return a;
	return b;
}

void	dijkstra(int nod)
{
	t_list	*list;

	list = v[nod];
	while (list)
	{
		if (viz[list->node] == 0)
		{
			end->next = ft_create_queue(list->node);
			end = end->next;
			cost[list->node] = minim(cost[nod] + list->cost, cost[list->node]);
		}
		else if (cost[nod] + list->cost < cost[list->node])
		{
			cost[list->node] = cost[nod] + list->cost;
			viz[list->node] = 0;
			end->next = ft_create_queue(list->node);
			end = end->next;
		}
		list = list->next;
	}
	viz[nod] = 1;
}

int		main(void)
{
	int		i;
	int		x, y, c;
	t_queue	*last;

	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++)
	{
		v[i] = NULL;
		cost[i] = 2000000;
	}
	cost[1] = 0;
	for (i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &x, &y, &c);
		ft_insert_elem(&v[x], y, c);
	}
	begin = ft_create_queue(1);
	end = begin;
	while (begin)
	{
		dijkstra(begin->value);
		last = begin;
		begin = begin->next;
		free(last);
	}
	for (i = 2; i <= n; i++)
		if (cost[i] != 2000000)
			printf("%d ", cost[i]);
		else
			printf("0 ");
	printf("\n");
	//ft_test_print();
	return (0);
}