#include<fstream.h>

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
using namespace std;

long n,m;
struct muchie { long x,y,c;  
              } a[250001];  
long d[50001];

int main()
{       
    long i,j;
	fin>>n>>m;
	for(i=1;i<=m;i++)
		{ fin>>a[i].x>>a[i].y>>a[i].c;
          if(a[i].x==1) d[a[i].y]=a[i].c;  
        }    
    for(i=1;i<=n;i++)  
         if(d[i]==0) d[i]=250001;  
    	
	
	int gata=0; 
	while(!gata)
	 {
	     gata=1;
         for(int i=1; i<=m; i++)
	        if(d[a[i].y]>d[a[i].x]+a[i].c)
	         { gata=0;
	           d[a[i].y]=d[a[i].x]+a[i].c;
             }
      }         
      

	for(i=2;i<=n;i++)
		if(d[i]>=32000) fout<<"0 ";
             else fout<<d[i]<<" ";
	return 0;
}