#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

struct NOD { int nr,cost; };

const int INF=50005*1001;

vector<NOD> v[50005];

priority_queue<pair<int,int> >h;

int d[50005];

bool f[50005];

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int n,m,x,y,cost,i,c;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		v[x].push_back((NOD){y,c});	
	}
	for(i=2;i<=n;i++)
		d[i]=INF;
	d[1]=0;
	pair<int,int> aux;
	aux.first=0;
	aux.second=1;
	h.push(aux);
	for(i=1;i<=n;i++)
	{
		while( !h.empty() && f[x=h.top().second] )
			h.pop();
		if(h.empty()) break;
		h.pop();
		f[x]=true;
		for(size_t j=0;j<v[x].size();j++)
		{
			y=v[x][j].nr;
			if( d[y]>d[x]+v[x][j].cost)
			{
				d[y]=d[x]+v[x][j].cost;
				aux.first=-d[y];
				aux.second=y;
				h.push( aux );
			}
		}
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i]);
	return 0;
}