#include <cstdio>
#include <vector>
using namespace std;
vector < pair <int,int> > a[50009];
int n,m,v[500009],cost[50009];
bool ma[50009];

void bfs()
{
	int r=1;
	v[1]=1;
	for (int p=1;p<=r;ma[v[p]]=false,++p)
		for (int i=0;i<a[v[p]].size();++i)
			if (!cost[a[v[p]][i].first]||cost[a[v[p]][i].first]>cost[v[p]]+a[v[p]][i].second)
			{
				cost[a[v[p]][i].first]=cost[v[p]]+a[v[p]][i].second;
				if (!ma[a[v[p]][i].first])
				{
					ma[a[v[p]][i].first]=1;
					v[++r]=a[v[p]][i].first;
				}
			}
}

int main()
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	char s[6];
	int x,y,z;
	for (int i=1;i<=m;++i)
	{
		gets(s);
		x=(int)(s[0]-'0');
		y=(int)(s[2]-'0');
		z=(int)(s[4]-'0');
		a[x].push_back(make_pair(y,z));
	}
	bfs();
	for (int i=2;i<=n;++i)
		printf("%d ",cost[i]);
	printf("\n");
	return 0;
}