#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int infinity = 999999;

int n, m;

vector <int> graph[50001], cost[50001];

int finalD[50001];

void read()
{
	ifstream f;
	f.open("dijkstra.in");
	int a, b, c;
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		f >> a >> b >> c;
		graph[a].push_back(b);
		cost[a].push_back(c);
	}
	f.close();
}

void solveBF(int vertex)
{
	queue <int> q;
	int this_cost, nod1, nod2, current_length;

	for (int i = 1; i <= n; i++)
		finalD[i] = infinity;

	finalD[vertex] = 0;

	q.push(vertex);

	while (!q.empty())
	{
		nod1 = q.front();
		q.pop();
		current_length = graph[nod1].size();
		for (int i = 0; i < current_length; i++)
		{
			nod2 = graph[nod1][i];
			this_cost = cost[nod1][i];

			if (finalD[nod2] > finalD[nod1] + this_cost)
			{
				finalD[nod2] = finalD[nod1] + this_cost;
				q.push(nod2);
			}

		}
	}
}

void display(int vertex)
{
	ofstream g;
	g.open("Dijkstra.out");
	for (int i = 1; i <= n; i++)
	{
		if (i == vertex) continue;
			if (finalD[i] == infinity)	finalD[i] = 0;
		g << finalD[i] << ' ';
	}
	g << '\n';
	g.close();
}

int main()
{
	read();
	solveBF(1);
	display(1);
    return 0;
}