#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>	





typedef struct listNode
{
	listNode* next;
	listNode* prev;
	int el;
	int dist;
};

listNode* list[50000];
int n, m;

void insertNodeInList(listNode*& head, int el, int dist)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->dist = dist;
	node->el = el;

	if (head == NULL)
	{
		head = node;
		head->next = NULL;
		head->prev = NULL;
		return;
	}


	head->next = node;
	head->next->prev = head;
	head = head->next;
	head->next = NULL;
}

void getList()
{
	scanf("%d%d", &n, &m);

	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		insertNodeInList(list[a], b, c);
	}
}
void printList()
{
	for (int i = 1; i <= n; i++)
	{
		listNode* aux = list[i];
		printf("%d:", i);
		while(aux!=NULL)
		{
			printf("%d %d  ", aux->el, aux->dist);
			aux = aux->prev;
		}
		printf("\n");
	}
}


int dist[50000],prev[50000];
bool viz[50000];



void insertQuery(listNode*& start, listNode*& finish, int el,int dist)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->el = el;
	node->dist = dist;

	if (start == NULL)
	{
		node->next = NULL;
		node->prev = NULL; 
		start = node;
		finish = node;
		return;
	}

	listNode *aux = start;
	while (aux!=NULL && aux->dist < dist)
	{
		aux = aux->next;
	}
	if (aux == NULL)
	{
		finish->next = node;
		node->next = NULL;
		node->prev = finish;
		finish = finish->next;
		return;
	}

	if (aux->prev != NULL)
		aux->prev->next = node;
	else
		start = node;
	node->next = aux;
	node->prev = aux->prev;
	aux->prev = node;

	start;
}

void popQuery(listNode*& start, listNode*& finish)
{
	if (finish == start)
	{
		finish = NULL;
		free(start);
		start = NULL;
		return;
	}
	listNode* aux = start;
	start = start->next;
	start->prev = NULL;
	free(aux);
}

listNode* searchNode(listNode *start1,int node)
{
	while (start1->el != node)
		start1 = start1->next;
	return start1;
}
void dijsktra(listNode*& start, listNode*& finish)
{
	while (start != NULL)
	{
		int node = start->el;
		listNode* aux = list[node];

		popQuery(start, finish);
		while (aux != NULL)
		{
			int ok = 0;
			if ( dist[aux->el] > aux->dist + dist[node])
			{
				ok = 1;
				dist[aux->el] = aux->dist + dist[node];
				prev[aux->el] = node;
			}
			if (ok && viz[aux->el])
			{
				listNode* aux1 = searchNode(start, aux->el);
				listNode* aux2 = aux1;
				aux1 = aux1->prev;
				aux1->next = aux1->next->next;
				if(aux1->next!=NULL)
				aux1->next->prev = aux1;
				if (aux2 == finish)
				{
					finish = finish->prev;
					finish->next = NULL;
				}
				free(aux2);

				insertQuery(start, finish, aux->el, dist[aux->el]);
			}
			if (!viz[aux->el])
			{
				viz[aux->el] = 1;
				insertQuery(start, finish, aux->el, dist[aux->el]);
			}
			aux = aux->prev;
		}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	for (int i = 1; i <= n; i++)
		list[i] = NULL;

	getList();


	for (int i = 2; i <= n; i++)
		dist[i] = 'INF';


	listNode* start = NULL, * finish = NULL;
	insertQuery(start, finish, 1,0);
	viz[1] = 1;

	dijsktra(start, finish);


	for (int i = 2; i <= n; i++)
	{
		if (dist[i] != 'INF')
			printf("%d ", dist[i]);
		else
			printf("0 ");
	}
}