#include<cstdio>
#include<vector>
#define NMAX 50005
#define inf (1<<30)
#define swap2(a,b) poz[heap[a]]=b
#define vec G[minim][i].first
#define cost G[minim][i].second
using namespace std;
vector < pair<int,int> > G[NMAX];
int n,m,d[NMAX],heap[NMAX],poz[NMAX],k;
inline void up(int c)
{
	while(c>1)
	{
		if(d[heap[c/2]]>d[heap[c]])
		{
			swap2(c/2,c);
			swap2(c,c/2);
			swap(heap[c/2],heap[c]);
			c>>=1;
		}
		else
			break;
	}
}
inline void down(int c)
{
	int jos;
	while(c<=k)
	{
		jos=c;
		if(c*2<=k)
		{
			jos<<=1;
			if(jos+1<=k && d[heap[jos+1]]<d[heap[jos]])
				jos++;
		}
		else
			break;;
		if(d[heap[c]]>d[heap[jos]])
		{
			swap2(c,jos);
			swap2(jos,c);
			swap(heap[jos],heap[c]);
			c=jos;
		}
		else
			break;
	}
}
inline void dijkstra()
{
	int minim;
	for(int i=2;i<=n;i++)
		d[i]=inf;
	heap[++k]=1;
	poz[1]=1;
	while(k)
	{
		minim=heap[1];
		swap(heap[1],heap[k]);
		swap2(1,1);
		k--;
		down(1);
		 
		for(size_t i=0;i<G[minim].size();i++)
			if(d[vec]>d[minim]+cost)
			{
				d[vec]=d[minim]+cost;
				if(poz[vec])
					up(poz[vec]);
				else
				{
					heap[++k]=vec;
					poz[heap[k]]=k;
					up(k);
				}
			}
	}
}
inline void citire()
{
	scanf("%d %d",&n,&m);
	int x,y,z;
	while(m--)
	{
		scanf("%d %d %d",&x,&y,&z);
		G[x].push_back(make_pair(y,z));
	}
}
inline void afisare()
{
	for(int i=2;i<=n;i++)
		printf("%d ",d[i]!=inf?d[i]:0);
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra();
	afisare();
	return 0;
}