#include <bits/stdc++.h>
#define oo 1e9
using namespace std;


ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


int n, m;
int dist[50005];
bool inq[50005];


vector<pair <int, int> > edge[50005];
priority_queue <int, vector<int>, greater<int> > q;



void Dijkstra(int nodst)
{
	for (int i = 1; i <= n; i++)
		dist[i] = oo;
	dist[nodst] = 0;
	q.push(nodst);
	inq[nodst] = true;
	int nodac;
	while (!q.empty())
	{
		nodac = q.top();
		q.pop();
		inq[nodac] = false;

		for (auto i : edge[nodac])
		{
			if (dist[nodac] + i.second < dist[i.first])
			{
				dist[i.first] = dist[nodac] + i.second;
				if (!inq[i.first])
				{
					q.push(i.first);
					inq[i.first] = true;
				}
			}



		}

	}
}

int main()
{
	int x, y, cost;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> x >> y >> cost;
		edge[x].push_back({ y, cost });
	}
	Dijkstra(1);
	for (int i = 2; i <= n; i++)
	{
		if (dist[i] != oo)
			fout << dist[i] << " ";
		else fout << "0 ";
	}
	fin.close();
	fout.close();
	return 0;
}