#include<fstream>
#include<vector>
#define pb push_back
const int inf = 10000;

using namespace std;
const int maxn = 50800;
int viz[maxn],n,m,par[maxn],coada[maxn];
struct dat{
	int l,c;
};
vector <dat> a[maxn];



main(){
   freopen("dijkstra.in","r",stdin);
   freopen("dijkstra.out","w",stdout);
  
  int x,y,z;   

scanf("%d %d",&n,&m);
for(int k=0;k<=n;k++)viz[k]=-1;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
dat o;
o.c=z;o.l=y;
a[x].pb(o);
};
int ig=1,sg=1,nod,val;coada[1]=1;par[1]=0;
while(ig<=sg){
	nod = coada[ig];
	val = viz[nod]!=-1?viz[nod]:0;
	for(int i=0;i<a[nod].size();i++){
		if(viz[a[nod][i].l]>val+a[nod][i].c || viz[a[nod][i].l]==-1){
			coada[++sg]=a[nod][i].l;
			viz[a[nod][i].l]=val+a[nod][i].c;
		}
	}
	ig++;
}

//  printf("\n");

 for(int i=2;i<=n;i++)printf("%d ",viz[i]!=-1?viz[i]:0);
    
  
  
}