#include<stdio.h>
#include<vector>
#define infin 100000000
using namespace std;
int n,m,num,heap[50014],t[50014],dij[50014];
vector<int> v[50014];
vector<int> d[50014];
void percolate(int poz)
{
	int aj=poz>>1,aux;
	while(aj && dij[heap[poz]]<dij[heap[aj]])
	{
		aux=heap[poz];
		heap[poz]=heap[aj];
		heap[aj]=aux;
		t[heap[aj]]=aj;
		t[heap[poz]]=poz;
		poz=aj;
		aj=aj>>1;
	}
}

void sift(int poz)
{
    int aj,u,aux;
    while(poz<num)
	{
	   	aj=poz<<1;
		u=poz;
		if(aj<=num && dij[heap[aj]]<dij[heap[u]])
			u=aj;
		aj=(poz<<1)+1;
		if(aj<=num && dij[heap[aj]]<dij[heap[u]])
			u=aj;
		if(dij[heap[u]]<dij[heap[poz]])
		{
			aux=heap[u];
			heap[u]=heap[poz];
			heap[poz]=aux;
			t[heap[u]]=u;
			t[heap[poz]]=poz;
			poz=u;
		}
		else
			return;
	}
}

void dijstra(int nod)
{
    int i,j,key,nr;
	dij[nod]=0;
    nr=v[nod].size();
	for(i=0;i<nr;i++)
	{
		heap[++num]=v[nod][i];
		dij[heap[num]]=d[nod][i];
		t[v[num][i]]=num;
		percolate(num);
	}
	while(num)
	{
		nr=v[heap[1]].size();
		j=heap[1];
		for(i=0;i<nr;i++)
			if(dij[j]+d[j][i]<dij[v[j][i]])
			{
				key=v[j][i];
				if(dij[key]==infin)
				{
					dij[key]=dij[j]+d[j][i];
					heap[++num]=key;
					t[key]=num;
					percolate(num);
				}
				else
				{
					dij[key]=dij[j]+d[j][i];
					percolate(t[key]);
				}
			}
		t[heap[num]]=1;
		heap[1]=heap[num];
		num--;
		sift(1);
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int i,j,a,b,c;
	scanf("%d%d\n",&n,&m);
	for(i=1;i<=m;i++)
	{
        scanf("%d%d%d",&a,&b,&c);
		v[a].push_back(b);
		d[a].push_back(c);
	}
	for(i=1;i<=n;i++)
		dij[i]=infin;
	dijstra(1);
	for(i=1;i<=n;i++)
		if(dij[i]==infin)
			printf("0 ");
		else
			printf("%d ",dij[i]);
	return 0;
}