#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <cstring>

using namespace std;

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

const int Nmax = 50001;
const int oo = 0x3f3f3f3f;

vector < pair <int, int> > a[Nmax];
queue <int> Q;
bitset <Nmax> viz;

int n, m, i, x, y, c, d[Nmax], xc, xi;

void BFS (int xi)
{
	viz[1]=1; Q.push (1); d[xi]=0;
	while (!Q.empty())
	{
		xc=Q.front(); Q.pop();
		for (vector < pair <int, int> >::iterator it=a[xc].begin(); it!=a[xc].end(); ++it)
		{
			if (d[it->first]>d[xc]+it->second)
			{
				d[it->first]=d[xc]+it->second;
				if (viz[it->first]==0)
				{
					viz[it->first]=1;
					Q.push(it->first);
				}
			}
		}
	}
}

int main()
{
	fin >> n >> m;
	for (i=1; i<=m; i++)
	{
		fin >> x >> y >> c;
		a[x].push_back(make_pair(y, c));
	}
	memset (d, oo, sizeof d);
	BFS (1);
	for (i=2; i<=n; i++)
	{
		if (d[i]<oo) fout << d[i] << " ";
		else fout << "0 ";
	}
}