#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

fstream fin("dijkstra.in", ios::in);
fstream fout("dijkstra.out", ios::out);
#define MAXN  50005
#define INF 0x3f3f3f3f
vector <pair<int, int> > list[MAXN];
int n, dist[MAXN];

class compare{
public:
	bool operator() (int x, int y){
		return dist[x] > dist[y];
	}
};

priority_queue< int, vector<int>, compare > heap;

void read()
{
	int x, y, m, c;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
		fin >> x >> y >> c,
		list[x].push_back(make_pair(y, c));
}
void dijkstra(int start)
{
	memset(dist + 1, INF, n * sizeof(int));
	dist[start] = 0;
	heap.push(start);

	while (!heap.empty()){
		int node = heap.top();
		heap.pop();

		for (int i = 0, size = list[node].size(); i < size; i++){
			int new_node = list[node][i].first;
			if (dist[new_node] > dist[node] + list[node][i].second)
				dist[new_node] = dist[node] + list[node][i].second,
				heap.push(new_node);
		}
	}
}

int main()
{
	read();
	dijkstra(1);

	for (int i = 2; i <= n; i++)
		if (dist[i] != INF) fout << dist[i] << " ";
		else fout << 0 << " ";

		fin.close();
		fout.close();
		return 0;
}