#include<fstream>
#include<set>
#include<vector>

#define NMAX 50000
#define INF 2000000000

using namespace std;

int x, y, z, d[NMAX + 5], n, m;
bool u[NMAX + 5];
set<pair<int, int>> s;
vector<pair<int, int>> G[NMAX + 5];

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

void init()
{
	for (int i = 2; i <= NMAX; i++)
	{
		d[i] = INF;
	}
}

void elim_dub()
{
	while (!s.empty())
	{
		int nod = s.begin()->second;
		if (u[nod] == 1)
		{
			s.erase(s.begin());
		}
		else
		{
			break;
		}
	}
}

void dijkstra()
{
	init();

	s.insert(make_pair(0, 1));

	while (!s.empty())
	{
		elim_dub();

		if (s.empty())
		{
			break;
		}

		int nod = s.begin()->second;

		u[nod] = 1;

		for (int i = 0; i < G[nod].size(); i++)
		{
			int fiu = G[nod][i].second;
			int dist = G[nod][i].first;
			if (d[nod] + dist < d[fiu])
			{
				d[fiu] = d[nod] + dist;
				s.insert(make_pair(d[fiu], fiu));
			}
		}

	}

}

void afisare()
{
	for (int i = 2; i <= n; i++)
	{
		out << d[i] << " ";
	}
}

int main()
{
	in >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		in >> x >> y >> z;
		G[x].push_back(make_pair(z, y));
	}
	dijkstra();
	afisare();
	return 0;
}