#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define oo 0x3f3f3f3f

using namespace std;

int nodes;
vector < vector < pair <int, int > > > List;

void read(const char * buff_file)
{
	fstream f(buff_file, ios::in);
	f>>nodes;
	int edges;
	f>>edges;
	List.reserve(nodes+1);
	List.resize(nodes+1);
	
	int left, right, value;
	
	for (int i=1; i<=edges; ++i)
	{
		f>>left>>right>>value;
		List[left].push_back(make_pair(right, value));
	}
};

#define T i/2
#define L 2*i
#define R 2*i+1

int H[1000000];
int nh;
int * used;
int * dest;

void upheap(int i)
{
	if (dest[H[T]] < dest[H[i]])
	{
		swap(H[T], H[i]);
		upheap(T);
	}
};

void downheap(int i)
{
	int min=i;
	
	if (L <= nh)
		if (dest[H[L]] < dest[H[min]])
			min=L;
	if (R <= nh)
		if (dest[H[R]] < dest[H[min]])
			min=R;
	if (min != i)
	{
		swap(H[min], H[i]);
		downheap(min);
	}
};

void print(const char *out_file)
{
	fstream g(out_file, ios::out);
	for (int i=2; i<=nodes; ++i)
		if (dest[i] == oo)
			g<<"0 ";
		else
			g<<dest[i]<<" ";
}

void Dijkstra()
{
	read("dijkstra.in");	
	used=new int[nodes+1];
	for (int i=1; i<=nodes; ++i) used[i]=0;
	dest=new int[nodes+1];
	for (int i=1; i<=nodes; ++i) dest[i]=oo;
	
	//H[++nh]=1;
	
	for (vector< pair <int, int> >::iterator it=List[1].begin(); it < List[1].end(); it++)
	{
		dest[it->first]=it->second;
		H[++nh]=it->first;
	}
	
	while (nh > 0)
	{
		int x=H[1];
		if (dest[x] == oo)
			break;
		swap(H[1], H[nh]);
		--nh;
		downheap(1);
		if (used[x] == 0)
		{
			used[x]=1;
			for (vector< pair < int, int > >::iterator it=List[x].begin(); it < List[x].end(); it++)
			{
				if (dest[it->first] > dest[x] + it->second)
				{
					dest[it->first] = dest[x] + it->second;
					H[++nh]=it->first;
					upheap(nh);
				}
			}
		}
	}
	print("dijkstra.out");
};

int main()
{
	Dijkstra();
	return 0;
};