#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;
int pinf = 99999;

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;
fill(&d[0],&d[n+1],pinf);
fill(&viz[0],&viz[n+1],0);
//fill(&t[0],&t[n+1],prim);

//t[prim]=0;
d[prim]=0;
c.push(prim);
viz[prim]=1;

while(!c.empty())
{int nod=c.front();
c.pop();
viz[nod]=0;
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]==0)
	{viz[it->first]=1;
	c.push(it->first);
	//t[it->first]=nod;
	}}
}

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

}

/*void afisare()
{int lg,dr[100];
for(int i=1;i<=n;i++)
	if(i!=prim)
	{dr[0]=i;
	lg=0;
	while(t[dr[lg]])
	{lg++;
	dr[lg]=t[dr[lg-1]];}
	
	for(int j=lg;j>=0;j--)
		printf("%d ",dr[j]);
	printf("\n");
	}
}*/

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