#include<cstdio>
#define maxn 50005
#define inf (1<<30)
#include<vector>
#include<utility>
#include<algorithm>
#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;
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;
	}
}
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;
	}
}
void dijkstra()
{
	int minim;
	while(k)
	{
		minim=heap[1];
		swap(heap[1],heap[k]);
		poz[heap[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++;
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int i,x,y,z;
	scanf("%d %d",&n,&m);
	for(i=2;i<=n;i++)
		d[i]=inf;
	while(m--)
	{
		scanf("%d %d %d",&x,&y,&z);
		a[x].push_back(make_pair(y,z));
	}
	heap[++k]=1;
	poz[1]=1;
	dijkstra();
	for(i=2;i<=n;i++)
		if(d[i]!=inf)
			printf("%d ",d[i]);
		else
			printf("0 ");
	return 0;
}