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