#include <bits/stdc++.h>

using namespace std;

ifstream in;
ofstream out;

vector<vector <pair <int, int> > >edge;
vector<int> dist;
vector<bool> visited;

struct cmp
{
	bool operator()(int x, int y)
	{
		if (dist[x] > dist[y])
			return 1;
		else
			return 0;
	}
};

priority_queue<int, vector<int>, cmp> q;

void dijkstra(int start)
{
	visited[start] = 1;
	dist[start] = 0;
	q.push(start);
	while (!q.empty())
	{
		int curent;
		curent = q.top();
		q.pop();
		for (int i = 0; i < edge[curent].size(); i++)
		{
			int cost;
			int near;
			cost = edge[curent][i].second;
			near = edge[curent][i].first;
			dist[near] = min(dist[near], dist[curent] + cost);
			if (visited[near] == 0)
			{
				visited[near] = 1;
				q.push(near);
			}
		}
	}
}

int n,m;

int main()
{
	in.open("dijkstra.in");
	out.open("dijkstra.out");
	in >> n >> m;

	edge.resize(n + 1);
	dist.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		in >> x >> y >> z;
		edge[x].push_back(make_pair(y, z));
	}

	for (int i = 0; i < dist.size(); i++)
	{
		dist[i] = 999999999;
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++)
	{
		if (dist[i] != 999999999)
			out << dist[i];
		else
			out << "-1";
		out << " ";
	}
}