#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;
#define MAX 50005
#define INF 0x3f3f3f3f
#define min(a,b) (((a)<(b))?(a):(b))
int n,m,heap[MAX],poz[MAX],d[MAX],l;
vector<pair<int,int> > g[MAX];
bitset<MAX> viz;
void swapH(int a,int b)
{
	int aux=heap[a];
	heap[a]=heap[b];
	heap[b]=aux;
	poz[heap[a]]=a;
	poz[heap[b]]=b;
}
void upHeap(int k)
{
	while( (k>>1) && d[heap[k>>1]]>d[heap[k]] )
	{
		swapH(k,k>>1);
		k>>=1;
	} 
}
void downHeap(int p)
{
	int q=0;
	while(q!=p)
	{
		q=p;
		int x=q<<1;
		for (int i=0; i<=1; i++,x++)
			if(x<=l && d[heap[x]] < d[heap[p]] ) p=x;
		swapH(p,q);
	}
}
void dijkstra()
{
	for(int i=1;i<=n;i++)
	{
		d[i]=INF;
		heap[i]=poz[i]=i;
	}
	d[1]=0,l=n;
	while(l)
	{
		int top=heap[1];
		viz[heap[1]]=true;
		swapH(1,l);
		l--;	
		downHeap(1);
		for(vector<pair<int,int> >::iterator it=g[top].begin();it!=g[top].end();it++)
		{
			if(!viz[it->first]&&(d[it->first]>d[top]+it->second))
			{
				d[it->first]=d[top]+it->second;
				upHeap(poz[it->first]);
			}
		}
	}
}
int main()
{
	FILE* fin=fopen("dijkstra.in","r");
	FILE* fout=fopen("dijkstra.out","w");
	fscanf(fin,"%d %d\n",&n,&m);
	int x,y,c;
	for(int i=0;i<=m;i++)
	{
		fscanf(fin,"%d %d %d\n",&x,&y,&c);
		g[x].push_back(make_pair(y,c));
	}
	dijkstra();
	for(int i=2;i<=n;i++)
		fprintf(fout,"%d ",(d[i]==INF)?0:d[i]);;
	return 0;
}