#include<cstdio>
#include<vector>
#define maxn 50005
#define inf (1<<30)
#define swap2(a,b) poz[heap[a]]=b
using namespace std;
vector < pair<int,int> > a[maxn];
int n,m,d[maxn],heap[maxn],poz[maxn],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);
		vector < pair<int,int> > :: iterator it;
		it=a[minim].begin();
		while(it!=a[minim].end())
		{
			if(d[(*it).first]>d[minim]+(*it).second)
			{
				d[(*it).first]=d[minim]+(*it).second;
				if(poz[(*it).first])
					up(poz[(*it).first]);
				else
				{
					heap[++k]=(*it).first;
					poz[heap[k]]=k;
					up(k);
				}
			}
			it++;
		}
	}
}
inline void citire()
{
	scanf("%d %d",&n,&m);
	int x,y,z;
	while(m--)
	{
		scanf("%d %d %d",&x,&y,&z);
		a[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;
}