#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define NMAX 50010
#define LMAX 250000000

int n,m;
vector < pair<int, int> > g[NMAX];
int dist[NMAX];
queue <int> q;
bool inq[NMAX];

void read()
{
	int i;
	int x,y,z;

	ifstream fin("dijkstra.in");

	fin>>n>>m;
	for (i=1; i<=m; ++i)
	{
		fin>>x>>y>>z;
		g[x].push_back( make_pair(y,z) );
	}

	fin.close();
}

void dijkstra()
{
	int i,elem;
	vector < pair<int, int> > :: iterator it;

	for (i=2; i<=n; ++i)
		dist[i] = LMAX;

	q.push(1);
	while (!q.empty())
	{
		elem = q.front();

		for (it=g[elem].begin(); it!=g[elem].end(); ++it)
			if (dist[it -> first] > dist[elem] + it -> second)
			{
				dist[it -> first] = dist[elem] + it -> second;
				if (inq[it -> first] == 0)
				{
					q.push(it -> first);
					inq[it -> first] = 1;
				}
			}

		inq[elem] = 0;
		q.pop();
	}
}

void write()
{
	int i;

	ofstream fout("dijkstra.out");

	for (i=2; i<=n; ++i)
		if (dist[i] != LMAX)
			fout<<dist[i]<<" ";
		else
			fout<<"0 ";
	fout<<'\n';

	fout.close();
}

int main()
{
	read();
	dijkstra();
	write();

	return 0;
}