#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 1000000000
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
int n,m,cost[NMAX];
vector < pair<int,int> > v[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y,z;
	for (i=1; i<=n; i++)
		cost[i]=INF;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		v[x].pb(mp(y,z));
	}
}
void solve()
{
	cost[1]=0;
	queue <int> Q;
	int i,x,x1,y1;
	Q.push(1);
	while (!Q.empty())
	{
		x=Q.front();
		Q.pop();
		for (i=0; i<v[x].size(); i++)
		{
			x1=v[x][i].f;
			y1=v[x][i].s;
			if (cost[x1]>cost[x]+y1)
			{
				cost[x1]=cost[x]+y1;
				Q.push(x1);
			}
		}
	}
}
void show()
{
	int i;
	for (i=2; i<=n; i++)
		printf("%d ",cost[i]);
	printf("\n");
}
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	read();
	solve();
	show();
	return 0;
}