#include<fstream.h>
const int pinf=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<=n;i++) 
d[i]=pinf;
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 solve(int prim)
{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=1;i<=n;i++)
if(i!=prim)
if(d[i]!=pinf)       
h<<d[i]<<" ";
else      
h<<"0 ";} 
int main()
{read(1);
solve(1);
return 0;}