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

#define inf 99999

typedef struct Edge {
	int name[100];
	int weight[100];
	int numNeighbours;
} Edge;

int queue[1000];
int indexQueue;
int dist[100000];
int numNodes, numEdges;

Edge* build(const char* filename)
{
	FILE* f = fopen(filename, "r");
	fscanf(f, "%d%d", &numNodes, &numEdges);
	Edge* nodes = (Edge*)malloc(numNodes * sizeof(Edge));
	for (int i = 1; i <= numNodes; i++)
		nodes[i].numNeighbours = 0;
	for (int i = 1; i <= numEdges; i++) {
		dist[i] = inf;
		int a, b, c;
		fscanf(f, "%d%d%d", &a, &b, &c);
		nodes[a].name[nodes[a].numNeighbours] = b;
		nodes[a].weight[nodes[a].numNeighbours] = c;
		(nodes[a].numNeighbours)++;
	}
	fclose(f);
	return nodes;
}

void dijsktra(Edge* nodes, const char* filename)
{
	int visited[50000] = {0};
	dist[1] = 0;
	visited[1] = 1;
	queue[0] = 1;
	indexQueue++;
	while (indexQueue) {
		int u = queue[0];
		visited[u] = 0;
		for (int i = 0; i < nodes[u].numNeighbours; i++) {
			int v = nodes[u].name[i];
			if (dist[v] > dist[u] + nodes[u].weight[i]) {
				dist[v] = dist[u] + nodes[u].weight[i];
				if (visited[v] == 0) {
					visited[v] = 1;
					queue[indexQueue] = v;
					indexQueue++;
				}
			}
		}
		for (int i = 0; i < indexQueue - 1; i++)
			queue[i] = queue[i + 1];
		indexQueue--;
	}
	FILE* g = fopen(filename, "w");
	for (int i = 2; i <= numNodes; i++)
		if (dist[i] == inf)
			fprintf(g, "0 ");
		else
			fprintf(g, "%d ", dist[i]);
	fclose(g);
}

int main(int argc, char** argv)
{
	Edge* nodes = build("dijkstra.in");
	dijsktra(nodes, "dijkstra.out");
	return 0;
}