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


#define type int
#define INT 2147483647
typedef struct listNode
{
	listNode* next;
	type el;
	int cost;
};


int n, m;



void insertNode(listNode*& vecini, int el,int cost)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->el = el;
	node->cost = cost;
	node->next = NULL;

	if (vecini == NULL)
	{
		vecini = node;
		return;
	}

	node->next = vecini;
	vecini = node;
	
}
void citireListaMuchii(FILE* fin,listNode**& vecini)
{
	int x, y,z;
	for (int i = 0; i < m; i++)
	{
		fscanf(fin, "%d%d%d", &x, &y,&z);
		insertNode(vecini[x], y,z);
		insertNode(vecini[y], x,z);
	}
}

int pop_min(int* dist, bool* prelucrat)
{
	int min = INT;
	int index = -1;
	for (int i = 1; i <= n; i++)
	{
		if (!prelucrat[i] && dist[i] <= min)
		{
			min = dist[i];
			index = i;
		}
	}
	return index;
}
void Dijsktra(listNode** vecini,int first)
{
	int* dist = (int*)malloc(sizeof(int) * (n + 1));
	int* parinte = (int*)malloc(sizeof(int) * (n + 1));
	listNode* list = NULL;
	bool* vizitat = (bool*)malloc(sizeof(bool) * (n + 1));

	for (int i = 1; i <= n; i++)
	{
		dist[i] = INT;
		vizitat[i] = 0;
		parinte[i] = -1;
	}
	dist[first] = 0;
	int length = n;
	while (length != 0)
	{
		int u = pop_min(dist, vizitat);
		if (u != -1)
		{
			vizitat[u] = 1;
			listNode* p = vecini[u];
			while (p != NULL)
			{
				if (!vizitat[p->el] && dist[u] + p->cost < dist[p->el])
				{
					dist[p->el] = dist[u] + p->cost;
					parinte[p->el] = u;
				}
				p = p->next;
			}
		}
		length--;
	}

	FILE* fout = fopen("dijsktra.out", "w");
	for (int i = 2; i <= n; i++)
	{
		if (dist[i] != INT)
		fprintf(fout,"%d ", dist[i]);
		else
			fprintf(fout, "0 ");
	}
}
int main()
{
	listNode** vecini=NULL;
	FILE* fin = fopen("dijsktra.in", "r");
	if (fin == NULL)
		exit(0);
	fscanf(fin, "%d%d", &n, &m);
	vecini = (listNode**)malloc(sizeof(listNode*) * (n + 1));
	for (int i = 1; i <= n; i++)
	{
		vecini[i] = NULL;
	}
	citireListaMuchii(fin, vecini);
	Dijsktra(vecini, 1);
}