#include <stdio.h>
#include <vector.h>
#define INF 2000000000
#define r 50001
FILE *f=fopen ("dijkstra.in", "r");
FILE *g=fopen ("dijkstra.out", "w");
struct nod { int x,c; } t;
vector <nod> v[r];
int H[r],P[r],d[r];
int n,m,k,i;

void swap(int &a, int &b)
{
	a=a^b;
	b=a^b;
	a=a^b;
}

void citire() {
int i,x;
fscanf (f, "%d%d", &n,&m);
for (i=1;i<=m;i++)
{
	fscanf (f, "%d%d%d", &x,&t.x,&t.c);
	v[x].push_back(t);
}
}

void downheap(int x) {
int fiu;
do
{
	fiu=0;
	if (2*x<=k)									fiu=2*k;
	if (2*x+1<=k && d[H[fiu]] > d[H[fiu+1]])	fiu=2*k+1;
	if (d[H[x]] < d[H[fiu]])					fiu=0;
	
	if (fiu)
	{
		swap (H[x], H[fiu]);
		P[H[x]]=x;
		P[H[fiu]]=fiu;
		x=fiu;
	}
}
while (fiu);
}

void upheap(int x) {
	while (x>1 && d[H[x]]<d[H[x/2]])
	{
		swap (H[x], H[x/2]);
		P[H[x]]=x;
		P[H[x/2]]=x/2;
		x/=2;
	}
}

void dijkstra_heap() {
int i,min;

for (i=2;i<=n;i++)
	{	d[i]=INF;	P[i]=-1;	}
P[1]=1;		H[++k]=1;	

while (k) 
{
	min=H[1];
	
	swap(H[1], H[k--]);
	P[H[1]]=1;
	downheap(1);
	
	for (i=0;i<v[min].size();i++)
		if (d[v[min][i].x]> d[min] + v[min][i].c)
		{
			d[v[min][i].x] = d[min] + v[min][i].c;
			if (P[v[min][i].x]!=-1)
				upheap(v[min][i].x);
			else
			{
				H[++k]=v[min][i].x;
				P[H[k]]=k;
				upheap(k);
			}
		}
}

}


int main() {
citire();
dijkstra_heap();

for (i=1;i<=n;i++)
	fprintf (g, "%d ", (d[i]==INF) ? 0 : d[i]);
return 0;
}