//#include"includeFiles.h"
//const int inf = 1<<30;

#include<stdio.h>
#include<fstream>
using namespace std;
#include<math.h>
#include<assert.h>

#define MAX 50001
#define INF 1000000000
int dist[MAX];
int nrNodes;


typedef struct FibHeap
{
	bool mark;
	int degree;
	int index;
	FibHeap *father,*left,*right,*child;
	//int nrNodes;
}FibHeap;


typedef struct graf
{
	int nod,et;
	graf* next;
}graf;

int N,M;
graf* a[MAX];
FibHeap* Min;
FibHeap* ARB[MAX];

bool T[MAX];



//-------------------------------FIBHEAP----------------------------------------


//if fh1 < fh2 then return a value <0, else return a value >=0
int compareNode(FibHeap* fh1, FibHeap* fh2)
{
	return dist[fh1->index] - dist[fh2->index];
};
int compareIndex(int index1, int index2)
{
	return dist[index1]-dist[index2];
}
FibHeap* createFibHeap(int new_index)
{
	FibHeap* H = new FibHeap(); 
	H->mark = false;
	H->degree = 0;
	H->index = new_index;
	H->father = NULL;
	H->left = H;
	H->right = H;
	H->child = NULL;
	//nrNodes = 1;
	return H;
};
void insertFibHeap(FibHeap** H, FibHeap* x)
{
	x->left = x;
	x->right = x;
	x->father = NULL;
	if((*H) != NULL)
	{
		//x->father = (*H)->father;
		x->right = (*H);
		x->left = (*H)->left;
		(*H)->left->right = x;
		(*H)->left = x;
		if(compareNode((*H), x) > 0)
		{
			//int nrNodes = x->nrNodes;
			(*H) = x;
			//(*H)->nrNodes+=x->nrNodes;
		}
	}
	else
		(*H) = x;
	

};
void printFibHeap(FibHeap* H, int level)
{
	if(!H)
		return;

	FibHeap* aux = H;
	do
	{
		for(int i=0;i<level;i++)
			printf("     ");
		printf("->%d %d\n",aux->index,aux->mark);

		if(aux->child != NULL)
			printFibHeap(aux->child, level+1);

		aux = aux->right;
	}while(aux != H);
};
void printFathersFibHeap(FibHeap* H, int level)
{
	if(!H)
		return;
	FibHeap* aux = H;
	do
	{
		for(int i=0;i<level;i++)
			printf("     ");
		printf("->%d %d (degree = %d)\n",aux->index,aux->mark,aux->degree);

	
		//if(aux->child != NULL)
		//	printFibHeap(aux->child, level+1);

		aux = aux->right;
	}while(aux != H);
};

//ATENTION! the pointer to the min node is not refreshed
void FibHeapLink(FibHeap* y, FibHeap* x)
{
	// remove y from the root list of H


	//y->father must be NULL because y must be in the root list of H
	if(y->father != NULL)
	{
		if(y->father->degree > 1)
			y->father->child = y->right;
		else
			y->father->child = NULL;
		y->father->degree--;
		y->father = NULL;
	}
	if(y != y->right)
	{
		y->right->left = y->left;
		y->left->right = y->right;
	}
	y->left = y;
	y->right = y;


	//make y a child of x, incrementing x->degree
	y->father = x;
	if(x->degree == 0)
		x->child = y;
	else
	{
		y->right = x->child;
		y->left = x->child->left;
		x->child->left->right = y;
		x->child->left = y;
	}
	x->degree++;

	//mark[y] = false
	y->mark = false;
};

void consolidate(FibHeap** H)
{
	//int nrNodes = (*H)->nrNodes;
	//float dn = D(nrNodes);
	FibHeap *A[MAX];
	for(int i=0;i<MAX;i++)
		A[i] = NULL;

	FibHeap* aux = (*H);
	do
	{
		FibHeap* aux2 = aux->right;
		if(aux2->right->father!=NULL)
		{
			printf("---------------------------------------------\n");

			printf("aux->mark = %d, aux->index = %d, aux->degree = %d\n",aux->mark, aux->index, aux->degree);
			printf("aux2->mark = %d, aux2->index = %d, aux2->degree = %d\n",aux2->mark, aux2->index, aux2->degree);
			printFathersFibHeap(*H, 0);

			printf("---------------------------------------------\n");
		}
		if(aux2->father!=NULL)
		{
			printf("aux2->mark = %d, aux2->index = %d, aux2->degree = %d\n",aux2->mark, aux2->index, aux2->degree);
			printf("---------------------------------------------\n");

			printFathersFibHeap(*H, 0);

			printf("---------------------------------------------\n");
	//		assert(false);
		}
		int deg = aux->degree;
		FibHeap* aux3 = aux;
		while(A[deg] != NULL)
		{
			//union 2 trees with the same degree
			if(compareNode(aux3,A[deg])>=0)
			{
				//if(aux3 == (*H))
					//(*H) = A[deg];
				if(aux2 == aux3)
					aux2 = aux2->right;
				FibHeapLink(aux3,A[deg]);
				aux3 = A[deg];
			}
			else
			{
				//if(A[deg] == (*H))
				//	(*H) = aux3;
				if(aux2 == A[deg])
					aux2 = aux2->right;
				FibHeapLink(A[deg],aux3);
			}
	//		A[deg]->father = NULL;
			A[deg] = NULL;
			deg++;
		}
		A[deg] = aux3;
		A[deg]->father = NULL;

		aux = aux2;// aux3->right;
	}while(aux != A[aux->degree]);//(*H));

	(*H) = NULL;
	for(int i=0;i<MAX;i++)
	{
		if(A[i]!=NULL)
			insertFibHeap(H,A[i]);
	}
		
	//(*H)->nrNodes = nrNodes;

};

int extractMin(FibHeap** H)
{
	int index = (*H)->index;

	if((*H)!=NULL)
	{
	    nrNodes--;// = (*H)->nrNodes - 1;

		FibHeap* aux = (*H)->child;
		if(aux!=NULL)
		{
			do
			{
				FibHeap* aux2 = aux->right;
				//add aux to the list of H
				if(aux->father)
				{
					if(aux->father->degree == 1)
						aux->father->child = NULL;
					else
						aux->father->child = aux->right;
					aux->father->degree--;
					aux->father = NULL;
				}
				if(aux!=aux->right)
				{
					aux->right->left = aux->left;
					aux->left->right = aux->right;
				}
				else
					aux2 = NULL;


				aux->right = (*H);
				aux->left = (*H)->left;
				(*H)->left->right = aux;
				(*H)->left = aux;

				aux = aux2;
			}while(aux != NULL);
		}
		//remove min from the root list of H
		if((*H)!=(*H)->right)
		{
			(*H)->left->right = (*H)->right;
			(*H)->right->left = (*H)->left;
			FibHeap* aa = (*H)->right;

			(*H)->left = NULL;
			(*H)->right = NULL;
			(*H) = aa;
			consolidate(H);
		}
		else
			(*H) = NULL;
		
	}

	return index;
};


void cutFibHeap(FibHeap* H, FibHeap* x, FibHeap* y)
{
	//remove x from the child list of y, decrementig y->degree
	if(y->child == NULL)
		return;
	
	if(y->degree == 1)
	{
		if(y->child == x)
			y->child = NULL;
	}
	else
	{
		if(y->child == x)
			y->child = x->right;
		x->right->left = x->left;
		x->left->right = x->right;
	}

	y->degree--;
	x->father = NULL;
	x->left = x;
	x->right = x;

	//add x to the root list of H
	x->left = H->left;
	x->right = H;
	H->left->right = x;
	H->left = x;

	x->mark = false;
};
void cascadingCutFibHeap(FibHeap* H, FibHeap* y)
{
	FibHeap* z = y->father;
	if(z != NULL)
	{
		if(y->mark == false)
			y->mark = true;
		else
		{
			cutFibHeap(H,y,z);
			cascadingCutFibHeap(H,z);
		}
	}
};
void decreaseKeyFibHeap(FibHeap** H, FibHeap* x, int new_index)
{
	assert(compareIndex(new_index,x->index)<=0);
	x->index = new_index;
	
	FibHeap* y = x->father;
	if(y!=NULL && compareIndex(x->index,y->index)<0)
	{
		cutFibHeap(*H,x,y);
		cascadingCutFibHeap(*H,y);
	}
	if(compareIndex(x->index,(*H)->index)<0)
	{
		//int nrNodes = (*H)->nrNodes;
		(*H) = x;
		//(*H)->nrNodes = nrNodes;
	}
};

FibHeap* unionFibHeap(FibHeap* Min_fh1, FibHeap* Min_fh2)
{
	if(!Min_fh1)
		return Min_fh2;
	if(!Min_fh2)
		return Min_fh1;
	Min_fh1->right->left = Min_fh2->left;
	Min_fh2->left->right = Min_fh1->right;

	Min_fh1->right = Min_fh2;
	Min_fh2->left = Min_fh1;

	if(compareNode(Min_fh1,Min_fh2)<=0)
		return Min_fh1;
	return Min_fh2;
};

//returns the upper bound D(n) on the maximum degree of any code in an n-node Fibonacci heap
float D(int n)
{
	return ceil(log((float)n));
};
//------------------------------------------------------------------------------





//-------------------------------GRAF----------------------------------------

void adaug(int x,int y,int et)
{
	graf* aux = new graf();
	aux->et = et;
	aux->nod = y;
	aux->next = a[x];
	a[x] = aux;
}
//------------------------------------------------------------------------------
void read()
{
	ifstream f("dijkstra.in");
	f>>N>>M;
	int x,y,z;
	for(int i=0;i<M;i++)
	{
		f>>x>>y>>z;
		adaug(x-1,y-1,z);
	}
	f.close();
	T[0] = true;
	dist[0] = 0;
	for(int i=1;i<N;i++)
	{
		T[i] = false;
		dist[i] = INF;
	}
	graf* aux = new graf();
	aux = a[0];
	while(aux)
	{
		dist[aux->nod] = aux->et;
		aux = aux->next;
	}


	Min = NULL;
	nrNodes = 0;
	for(int i=1;i<N;i++)
	{
		FibHeap *aux2 = createFibHeap(i);
		nrNodes++;
		insertFibHeap(&Min,aux2);
		ARB[i-1] = aux2;
	}
}

void solve()
{
	int xp=INF;
	while(Min && nrNodes>1)
	{
		xp = extractMin(&Min);
		T[xp] = true;
		graf* aux = new graf();
		aux = a[xp];
		while(aux)
		{
			if(!T[aux->nod] && dist[aux->nod]>(dist[xp]+aux->et))
			{
				dist[aux->nod] = dist[xp]+aux->et;
				assert(Min!=NULL);
				decreaseKeyFibHeap(&Min,ARB[aux->nod-1],aux->nod);
			}
			aux = aux->next;
		}
	}

	ofstream g("dijkstra.out");
	for(int i=1;i<N;i++)
		if(dist[i]!=INF)
			g<<dist[i]<<" ";
		else
			g<<"0 ";
	g.close();
}

int main()
{
	read();
	solve();

	return 0;
}