#include<stdio.h>
#include<algo.h>
#include<queue>
#include<vector>
#define max 50005
using namespace std;
vector<pair<int,int> >g[max];

int d[max],n,m,t[max],prim;
const int pinf = 9999;

void citire()
{int x,y,c;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
	{scanf("%d %d %d",&x,&y,&c);
	g[x].push_back(make_pair(y,c));}}

void dijkstra()
{bool viz[max];
queue<int>c;

memset(d, pinf, sizeof(d)); 
memset(viz, false, sizeof(viz));

d[prim]=0;
c.push(prim);
viz[prim]=true;

while(!c.empty())
{int nod=c.front();
c.pop();
viz[nod]=false;
for(vector<pair<int,int> >::iterator it=g[nod].begin();it!=g[nod].end();++it)
	if(d[nod] + it->second < d[it->first]) 
	{d[it->first]=it->second+d[nod];
	if(viz[it->first]==false)
	{viz[it->first]=true;
	c.push(it->first);
	
	}}
}

for(int i=2;i<=n;i++)
if(d[i]<pinf)printf("%d ",d[i]);
else
printf("%d ",0);	
}


int main ()
{freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
prim=1;
citire();
dijkstra();

return 0;
}