#include<stdio.h> 
#include<fstream.h>
#include<iostream.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<=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) 
{ 
for(i=1;i<=n;i++)  
if(d[i]==0)   
d[i]=pinf; 
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==1);

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; }