#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define Max 9999999
vector <int> cost(50005,Max);
vector <bool> ut(50005);

struct cmp
{
	bool operator () (const int x,const int y) const
	{
		return cost[x]>cost[y];
	}
};
typedef pair <int,int> nc;
vector <nc> a[50005];
priority_queue <int,vector <int>,cmp> heap;
int n,m;
void hs()
{
	vector <nc> ::iterator it;
	heap.push(1);cost[1]=0;
	while(!heap.empty())
	{
		int nod=heap.top();heap.pop();
		ut[nod]=false;
		for(it=a[nod].begin();it!=a[nod].end();it++)
		{
			if(cost[it->first]<=cost[nod]+it->second)
				continue;
			cost[it->first]=cost[nod]+it->second;
			if(!ut[it->first])
			{
				heap.push(it->first);
				ut[it->first]=true;
			}
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		a[x].push_back(nc(y,c));
	}
	hs();
	for(int i=2;i<=n;i++)
	{
		if(cost[i]==Max)
		{
			printf("0 ");
			continue;
		}
		printf("%d ",cost[i]);
	}
	return 0;
}