#include <stdio.h>
#include <vector>
#include <queue>

#define maxn 50000
#define mp make_pair

using namespace std;

struct nod
{
	int nr;
	int cost;
};

vector<nod> g[maxn];
int n, m, viz[maxn], cost[maxn];

void citire()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%d%d", &n, &m);

	int a, b, k;
	nod c;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d", &a, &b, &k);
		c.nr=b;
		c.cost=k;
		g[a].push_back(c);
	}
}

void dijkstra()
{
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int x = q.front();
		for(int i=0;i<g[x].size();i++)
		{
			if(cost[g[x][i].nr]>cost[x] + g[x][i].cost)
			{
				cost[g[x][i].nr] = cost[x] + g[x][i].cost;
				q.push(g[x][i].nr);
			}
		}
		q.pop();
	}
}

int main()
{
	citire();

	for(int i=2;i<=n;i++)
	{
		cost[i]=50001;
	}

	dijkstra();

	for(int i=2;i<=n;i++)
	{
		printf("%d ", cost[i]);
	}

	return 0;
}