#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define N 50005
#define inf 0x3f3f3f3f
#define val first
#define cost second

using namespace std;

vector<pair<int, int> > L[N];
queue<int> Q;
int D[N];

void bfs()
{
	for (Q.push(1); !Q.empty(); Q.pop())
		for (vector<pair<int, int> >::iterator it = L[Q.front()].begin(); it != L[Q.front()].end(); ++it)
			if (D[Q.front()] + it->cost < D[it->val])
			{
				D[it->val] = D[Q.front()] + it->cost;
				Q.push(it->val);
			}
}

int main()
{
	int n, m, x, y, c;
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	memset(D, inf, sizeof(D));
	D[1] = 0;
	fin >> n >> m;

	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y >> c;
		L[x].push_back(make_pair(y, c));
	}
	bfs();

	for (int i = 2; i <= n; ++i)
		fout << (D[i] < inf ? D[i] : 0) << ' ';

    return 0;
}