#include <cstdio>
#include <vector>
using namespace std;
#define nmax 50010
#define inf 1<<30
#define f first
#define s second

vector <pair<int, int> > g[nmax];
int n, m, k, d[nmax], heap[nmax], poz[nmax];

void swap(int a, int b)
{
	int c=heap[a];
	heap[a]=heap[b];
	heap[b]=c;
}

void heap_up(int nod)
{
	if (nod>1)
		if (d[heap[nod/2]]<d[heap[nod]]) 
		{
			swap(nod/2, nod);
			poz[heap[nod/2]]=nod;
			poz[heap[nod]]=nod/2;
			heap_up(nod/2);
		}
}

void heap_down(int nod)
{
	if (nod*2<=k)
	{
		int c=2*nod;
		if (c<k && d[heap[c+1]]<d[heap[c]]) c++;
		if (d[heap[nod]]>d[heap[c]])
		{
			swap(nod, c);
			poz[heap[nod]]=c;
			poz[heap[c]]=nod;
			heap_down(c);
		}
	}
}

void dijkstra()
{
	int i, j, p;
	for (i=2; i<=n; i++) d[i]=inf;
	k=1;
	heap[1]=1;
	poz[1]=1;
	while (k)
	{
		p=heap[1];
		swap(1, k);
		poz[heap[1]]=1;
		k--;
		heap_down(1);
		for (i=0; i<g[p].size(); i++)
		{
			j=g[p][i].f;
			d[j]=min(d[j], d[p]+g[p][i].s);
			if (!poz[j])
			{
				k++;
				heap[k]=j;
				poz[j]=k;
				heap_up(k);
			} else heap_up(poz[j]);
		}
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i, x, y, c;
	while (m--)
	{
		scanf("%d %d %d",&x,&y,&c);
		g[x].push_back(make_pair(y,c));
	}
	dijkstra();
	for (i=2; i<=n; i++) 
		if (d[i]==inf) printf("0 "); else printf("%d ",d[i]);
}