/*
	Dupa citirea numarului de varfuri(n) si de muchi(m), se citesc toate cele m muchii si se creeaza listele vecinilor in vector a 
	Vectorul d va retine in final costurile minime de la varful 1 la toate celelalte (d[i]= costul minim de la varful 1 la varful i)
	Initial d[1]=0 si d[k]=infinit , 2<=k<=n
	Pentru a rezolva problema vom utiliza o coada Q pentru a parcurge in latime graful utilizand principiul de minimalitate a lui BELLMAN
	Initial introducem in coada Q varful 1 , iar in final coada Q va fi vida
	Se vor afisa elementele vectorului de costuri minime d 
*/
#include<fstream>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("dijkstra.in"); ofstream g("dijkstra.out");
int n,m;
struct arc {int nod,cost;};
vector <arc> a[50001];
vector <int> d(50001,inf);
queue<int> Q;
void cit(),dijkstra(),scrie();
int main()
{	cit(); dijkstra(); scrie(); return 0;}
void cit()
{ 	f>>n>>m; arc e;
	for(register int x,i=1; i<=m; ++i,a[x].push_back(e)) f>>x>>e.nod>>e.cost;
}
void dijkstra()
{	Q.push(1); d[1]=0; 
	while(!Q.empty())
		{	int aux=Q.front(); Q.pop();
			for(unsigned int i=0; i<a[aux].size(); ++i) 
				{	int wcost=a[aux][i].cost, wnod=a[aux][i].nod;
					if(d[wnod]>d[aux]+wcost) {d[wnod]=d[aux]+wcost; Q.push(wnod);}
				}
		}
}
void scrie()
{	for(register int i=2; i<=n; ++i) g<<(d[i]==inf?0:d[i])<<' '; g<<'\n';}