#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
queue<int> q;
struct str
{
	int x,c;
	str()
		{
			x=c=0;
		}
	str (int xx,int cc)
		{
			x=xx;
			c=cc;
		}
};
vector<str> v[50005];
bool inc[50005];
int r[50005];
int main()
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	int n,m;
	scanf ("%d%d",&n,&m);
	for(int i=0;i<50005;i++){
		r[i]=2000000000;
	}
	while(m--){
		int x,y,z;
		scanf ("%d%d%d",&x,&y,&z);
		v[x].push_back (str (y,z));
	}
	q.push (1);
	inc[1]=1;
	r[1]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		inc[x]=0;
		for(vector<str>::iterator it=v[x].begin();it!=v[x].end();it++)
			if(r[x]+it->c<r[it->x]){
				r[it->x]=r[x]+it->c;
				if(!inc[it->x]){
					inc[it->x]=1;
					q.push (it->x);
				}
			}
	}
	for(int i=2;i<=n;i++)
		printf ("%d ",r[i]);
	return 0;
}