#include <fstream>
#include <vector>
#include <set>
#define INF 2147483647 // long int max
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct dest_node
{
	int node;
	int len;
	dest_node() {};
	dest_node(int n, int l) : node(n), len(l) {};
};

struct comp
{
	bool operator() (const dest_node &n1, const dest_node &n2) const
	{
		return n1.len < n2.len;
	}
};

int n, m;
vector<dest_node> G[50005];

void Dijkstra()
{
	long dis[50005];
	dis[1] = 0;
	for (int i = 2; i <= n; i++) 
		dis[i] = INF;
	set <dest_node,comp> v;
	v.insert(dest_node(1, 0));
	while (!v.empty())
	{
		auto it = v.begin();
		int node = it -> node,
			len = it -> len;
		v.erase(it);
		for (auto nbr : G[node])
		{
			long nw = dis[node] + nbr.len;
			if (nw < dis[nbr.node])
			{
				if (dis[nbr.node] != INF)
					v.erase(dest_node(nbr.node, dis[nbr.node]));
				v.insert(dest_node(nbr.node, nw));
				dis[nbr.node] = nw;
			}
		}
			
	}
	for (int i = 2; i <= n; i++)
		g << (dis[i] == INF ? 0 : dis[i]) << " ";
}

int main()
{
	{
		int x, y,z;
		f >> n >> m;
		for (int i = 0; i < m; i++)
		{
			f >> x >> y >> z;
			G[x].push_back(dest_node(y, z));
		}
	}
	Dijkstra();
	return 0;
}