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

int n,m;
vector <int> g[NMAX],c[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(y);
		c[x].push_back(z);
	}

	fin.close();
}

void dijkstra()
{
	int i,elem;

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

	q.push(1);
	while (!q.empty())
	{
		elem = q.front();
		for (i=0; i<(int)g[elem].size(); ++i)
			if (dist[g[elem][i]] > dist[elem] + c[elem][i])
			{
				dist[g[elem][i]] = dist[elem] + c[elem][i];
				if (inq[g[elem][i]] == 0)
				{
					q.push(g[elem][i]);
					inq[g[elem][i]] = 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;
}