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

#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));
	}
	f.close();
};

int used[50005];
int dest[50005];

struct cmp
{
	bool operator()(const int &left, const int &right) const
	{
		if (dest[left] < dest[right])
			return 0;
		else
			return 1;
	}
};

int nr;

void Dijkstra()
{
	priority_queue<int, vector<int>, cmp> Q;
	
	for (int i=1; i<=nodes; ++i)
		dest[i]=oo;
	dest[1]=0;
	
	Q.push(1);
	nr=1;
	
	while (nr)
	{
		int x=Q.top();
		Q.pop(); 
		--nr;
		if (dest[x] == oo)
			break ;
		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;
					if (used[it->first] == 0)
					{
						Q.push(it->first);
						++nr;
					}
				}
			}
		}
	}
};

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]<<" ";
}

int main()
{
	read("dijkstra.in");
	Dijkstra();
	print("dijkstra.out");
	return 0;
};