#include<cstdio>
#include<vector>
using namespace std;
#define inf 500000
#define Mmax 50001
#define F(i,EXP) for(register int i=1;(EXP);++i)
#define W(EXP) while(EXP)
int d[Mmax],viz[Mmax],ok=1,minim,poz,n,m,x,y,c;
vector<int> a[Mmax];
int main()
{freopen("dijkstra.in","rt",stdin);
 freopen("dijkstra.out","wt",stdout);
 scanf("%d%d",&n,&m);
 F(i,i<=n+1) F(j,j<=n+1) a[i].push_back(inf);
 F(i,i<=m) {scanf("%d%d%d",&x,&y,&c); a[x][y]=c;}
 F(i,i<=n) d[i]= !a[1][i]? inf : a[1][i]; 
 viz[1]=1;
 W(ok) 
    {minim=inf;
	 F(i,i<=n) if(!viz[i] && minim>d[i]) {minim=d[i];poz=i;}
	 if(minim!=inf)
		 {viz[poz]=1;
	      F(i,i<=n) if(!viz[i] && d[i]>d[poz]+a[poz][i]) d[i]=d[poz]+a[poz][i]; 
		 }
	  else ok=0;
	}
 F(i,i<n) printf("%d ",d[i+1]);printf("\n");
 return 0;
}