#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<bitset>
using namespace std;
#define Max 9999999
#define usi unsigned short int
vector <int> cost(50005,Max);
bitset <50005> ut;
class nc
{
public:
	usi nod,costInit;
	nc(const usi &n,const usi &c)
	{
		nod=n;costInit=c;
	}
};
struct cmp
{
	bool operator () (const usi &x,const usi &y) const
	{
		return cost[x]>cost[y];
	}
};
vector <nc> a[50005];
priority_queue <usi,vector <usi>,cmp> heap;
usi n;
int m;
void hs()
{
	vector <nc> ::iterator it;
	heap.push(1);cost[1]=0;
	usi nod;
	while(!heap.empty())
	{
		nod=heap.top();heap.pop();
		ut[nod]=false;
		for(it=a[nod].begin();it!=a[nod].end();it++)
		{
			if(cost[it->nod]<=cost[nod]+it->costInit)
				continue;
			cost[it->nod]=cost[nod]+it->costInit;
			if(!ut[it->nod])
			{
				heap.push(it->nod);
				ut[it->nod]=true;
			}
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%hd%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		usi x,y,c;
		scanf("%hd%hd%hd",&x,&y,&c);
		a[x].push_back(nc(y,c));
	}
	hs();
	for(usi i=2;i<=n;i++)
	{
		if(cost[i]==Max)
		{
			printf("0 ");
			continue;
		}
		printf("%d ",cost[i]);
	}
	return 0;
}