#include <cstdio>
#include <cmath>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>

#define NMAX 50003
using namespace std;

FILE* fin, * fout;

int n,m;
int dMin[NMAX];
int viz[NMAX];

struct muchie {
	int x, cost;
	bool operator()(muchie a, muchie b)
	{
		return a.cost > b.cost;
	}
};
vector<muchie>graf[NMAX];


int main()
{
	fin = fopen("dijkstra.in", "r");
	fout = fopen("dijkstra.out", "w");
	
	fscanf(fin, "%d %d", &n,&m);
	for (int i = 1; i <= m; i++)
	{
		int x, y, cost;
		fscanf(fin, "%d %d %d", &x, &y, &cost);
		graf[x].push_back({ y,cost });

	}
	for (int i = 1; i <= n; i++)
	{
		dMin[i] = INT_MAX;
	}

	priority_queue<muchie, vector<muchie>, muchie>q;
	q.push({ 1,0 });
	dMin[1] = 0;
	while (!q.empty())
	{
		int nodPrec = q.top().x;
		int cPrec = q.top().cost;
		if (viz[nodPrec])
		{
			q.pop();
			continue;
		}
		viz[nodPrec] = true;
		for (int i = 0; i < graf[nodPrec].size(); i++)
		{
			int nd = graf[nodPrec][i].x;
			int cst = graf[nodPrec][i].cost;
			if (!viz[nd] && dMin[nd] > cPrec + cst)
			{
				dMin[nd] = cPrec + cst;
				q.push({ nd,dMin[nd] });
			}
		}
	}
	for (int i = 2; i <= n; i++)
	{
		if (dMin[i] == INT_MAX)
		{
			dMin[i] = 0;
		}
		fprintf(fout, "%d ", dMin[i]);
	}
	return 0;
}