#include<fstream.h>
const int inf=0x3f3f3f3f;
ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
struct muchie{
long x,y,c;             
}G[500001];
long d[500001],i,n,m,ok;
void read(int prim)
{ f>>n>>m;
for(i=1;i<=m;i++)
{f>>G[i].x>>G[i].y>>G[i].c;
if(G[i].x==prim)       
d[G[i].y]=G[i].c; }}
void M(int prim)
{for(i=1;i<=n;i++)
if(d[i]==0)
d[i]=inf;
do{ok=1;  
for(i=1;i<=m;i++) 
if(d[G[i].y] > d[G[i].x]+G[i].c)
{d[G[i].y] = d[G[i].x]+G[i].c;
ok=0;}}
while(!ok);
for(i=2;i<=n;i++)
if(d[i]!=inf)      
h<<d[i]<<" ";
else     
h<<"0 ";}
int main()
{read(1);
M(1);
return 0;}