#include<fstream>
#define infinit 10000000
using namespace std;
int n,m,a[1000][1000];

void citire(){
	ifstream in("dijkstra.in");
	in>>n>>m;
	int i,j,k,cost;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=infinit;
	for(i=1;i<=m;i++){
		in>>j>>k>>cost;
		a[j][k]=cost;
	}
}

void dijkstra(){
	int k,i;
	for(k=2;k<=n;k++)
		for(i=2;i<=n;i++)
			if(i!=k)
				if(a[1][i]>a[1][k]+a[k][i])
					a[1][i]=a[1][k]+a[k][i];
	for(i=2;i<=n;i++)
		if(a[1][i]==infinit)
			a[1][i]=0;	
}

void afisare(){
	int i;
	ofstream out("dijkstra.out");
	for(i=2;i<=n;i++)
		out<<a[1][i]<<" ";
	out.close();
}

int main(){
	citire();
	dijkstra();
	afisare();
	return 0;
}