#include <fstream>
#include <queue>
#include <vector>
using namespace std;
int cost[100001];
queue <int> Nod;
vector <pair<int,int>> V[50001];
int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int n, m, a, b, c;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> a >> b >> c;
		V[a].push_back(make_pair(b, c));
	}
	for (int i = 2; i <= n; i++)
		cost[i] = 1000000005;
	cost[1] = 0;
	Nod.push(1);
	int nc=0;
	while (!Nod.empty())
	{
	    if(nc==n-1)
            break;
		int currentNode = Nod.front();
		Nod.pop();
		nc++;
		for (auto x : V[currentNode])
		{
			if (cost[x.first] > cost[currentNode] + x.second)
			{
				cost[x.first] = cost[currentNode] + x.second;
				Nod.push(x.first);
			}
		}
	}
	for (int i = 2; i <= n; i++)
        if(cost[i]==1000000005)
        	fout<<"0 ";
        else
			fout << cost[i] << " ";
	return 0;
}