#include<cstdio>
#include<vector>
#include<queue>
#define NMAX 50001
using namespace std;
typedef struct {
int nc;
int cost;
}nod;
bool operator<(nod x,nod y)
{
return x.cost>y.cost;
}
vector< nod > v[NMAX];
priority_queue< nod > q;
int i,j,n,k,m,d[NMAX],s[NMAX],x,y,c;
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
nod p;

for(;m>0;m--)
{
	scanf("%d%d%d",&x,&y,&c);
	p.nc=y;
	p.cost=c;
	v[x].push_back(p);
}
p.nc=1; p.cost=0;
q.push(p);
nod x;
while(!q.empty())
{
p=q.top();
q.pop();
if(s[p.nc]==0) 
{
s[p.nc]=1;
d[p.nc]=p.cost;

vector< nod >::iterator it;
	for(it=v[p.nc].begin();it!=v[p.nc].end();++it)
	{
		if(s[it->nc]==0)
		{
			x.nc=it->nc;
			x.cost=p.cost+it->cost;
			q.push(x);
		}
	}
}

}

for(i=2;i<=n;i++)
	printf("%d ",d[i]);
return 0;
}