#include <fstream>
#include <vector>

template <class type>
class Heap	//	all functions returning 0 on success, 1 on failure
{
protected:
	type *v;	//	indexing from 1
	int *heapToKey;
	int *keyToHeap;
	int numElem;
	int capacity;
	int keyCapacity;
	bool trackKeys;
	
	bool (*comp)(const type&, const type&);
	static bool basicMinComp(const type &a, const type &b)
	{
		return a < b;
	}
public:
	//	compFunction(a, b) returns 1 if the first arg should be placed closer to the top than the second; defaults to basic '<' operator
	//	if using keys, each key must be unique to a pushed node and each key must be positive and lower or equal to the heap's keyCapacity
	Heap(int maxSize, bool keepTrackOfKeys = 0, int maxKey=-1, bool (*compFunction)(const type&, const type&)=NULL)
	{
		if (maxKey == -1)
			maxKey = maxSize;
		keyCapacity = maxKey;
		if (compFunction == NULL)
			comp = this->basicMinComp;
		else
			comp = compFunction;
		trackKeys = keepTrackOfKeys;
		numElem = 0;
		capacity = maxSize;
		v = NULL;
		heapToKey = NULL;
		keyToHeap = NULL;
		try
		{
			v = new type[capacity+1];
		}
		catch (std::bad_alloc&)
		{
			throw;
			//	???
		}
		if (trackKeys)
		{
			try
			{
				heapToKey = new int[capacity+1];
				keyToHeap = new int[keyCapacity+1];
				
			}
			catch (std::bad_alloc&)
			{
				throw;
				//	???
			}
			for (int i = 0; i <= capacity; ++i)
				heapToKey[i] = -1;
			for (int i = 0; i <= keyCapacity; ++i)
				keyToHeap[i] = -1;
		}

	}
	~Heap()
	{
		if (v)
			delete [] v;
		if (heapToKey)
			delete [] heapToKey;
		if (keyToHeap)
			delete [] keyToHeap;
	}

	bool isTrackingKeys()
	{
		return trackKeys;
	}
	bool isEmpty()
	{
		return numElem <= 0;
	}
	int getNumElems()
	{
		return numElem;
	}
	bool isKeyInHeap(int key)
	{
		if ((!trackKeys) || (key < 0) || (key > keyCapacity))
			return 1;
		return keyToHeap[key] != -1;
	}

	//	n must be greater or equal to the number of elements currently in the heap
	bool setCapacity(int n)
	{
		if (n < numElem)
			return 1;	//	data loss if operation is executed

		type *newV;
		int *newHeapToKey = NULL;
		try
		{
			newV = new type[n+1];	//	indexing from 1
			if (trackKeys)
				newHeapToKey = new int[n+1];
		}
		catch (std::bad_alloc&)
		{
			return 1;	//	operation failed, but the old vectors remain unchanged
		}
		capacity = n;
		for (int i = 0; i <= numElem; ++i)
			newV[i] = v[i];
		if (trackKeys)
		{
			for (int i = 0; i <= numElem; ++i)
				newHeapToKey[i] = heapToKey[i];
			for (int i = numElem+1; i <= capacity; ++i)
				newHeapToKey[i] = -1;
		}
		delete [] v;
		v = newV;
		if (trackKeys)
		{
			delete [] heapToKey;
			heapToKey = newHeapToKey;
		}
		return 0;
	}
	//	n must be greater or equal to keyCapacity
	bool setKeyCapacity(int n)
	{
		if (!trackKeys)
			return 1;	//	keyCapacity is irrelevant if not using keys
		if (n < keyCapacity)
			return 1;	//	possible data loss if operation is executed

		int *newKeyToHeap = NULL;
		try
		{
			newKeyToHeap = new int[n+1];
		}
		catch (std::bad_alloc&)
		{
			return 1;	//	operation failed, but the old vector remains unchanged
		}
		for (int i = 0; i <= keyCapacity; ++i)
			newKeyToHeap[i] = keyToHeap[i];
		for (int i = keyCapacity+1; i <= n; ++i)
			newKeyToHeap[i] = -1;

		keyCapacity = n;
		delete [] keyToHeap;
		keyToHeap = newKeyToHeap;

		return 0;
	}

	bool push(const type &x, int key = -1)	//	key shouldn't already be in the heap and key should be between 0 and keyCapacity
	{
		if (numElem == capacity)
		//	return 1;	//	no more space
			if (setCapacity(capacity+1000))	//	making room for more elements
				return 1;
		if (key >= keyCapacity)
			if (setKeyCapacity(key))	//	making room to be able to handle larger keys
				return 1;
		v[++numElem] = x;
		if (trackKeys && (key != -1))
		{
			if (keyToHeap[key] != -1)
			{
				//	key already in the heap; erroneous behaviour if continuing
				remove(numElem);	//	removing the recently added value to undo to the state prior to the function call
				return 1;
			}
			heapToKey[numElem] = key;
			keyToHeap[key] = numElem;
		}
		tryUp(numElem);

		return 0;
	}
	bool removeByKey(int key)
	{
		if ((!trackKeys) || (keyToHeap[key] == -1))
			return 1;	//	key not pushed in the heap
		return remove(keyToHeap[key]);
	}
	bool pop(type *popped, int *keyPopped=NULL, bool removeAfterPop=1)
	{
		if (numElem == 0)
			return 1;	//	nothing to pop
		if (popped)
			*popped = v[1];
		if (keyPopped && trackKeys)
			*keyPopped = heapToKey[1];
		if (removeAfterPop)
			remove(1);
		return 0;
	}
	bool getValueAtKey(type *value, int key)
	{
		if ((!trackKeys) || (keyToHeap[key] == -1))
			return 1;	//	key not pushed in the heap
		*value = v[keyToHeap[key]];
		return 0;
	}
	bool updateElementByKey(const type &newX, int key)
	{
		if ((!trackKeys) || (keyToHeap[key] == -1))
			return 1;	//	key not pushed in the heap
		return updateElement(keyToHeap[key], newX);
	}
protected:
	void swap(int index1, int index2)
	{
		type t = v[index1];
		v[index1] = v[index2];
		v[index2] = t;
		if (trackKeys)
		{
			int iT = heapToKey[index1];
			heapToKey[index1] = heapToKey[index2];
			heapToKey[index2] = iT;
			keyToHeap[heapToKey[index1]] = index1;
			keyToHeap[heapToKey[index2]] = index2;
		}
	}
	void tryUp(int index)
	{
		while ((index > 1) && (comp(v[index], v[index/2])))
		{
			swap(index, index/2);
			index /= 2;
		}
	}
	void tryDown(int index)
	{
		int tryIndex = 1;
		while (tryIndex != 0)
		{
			int dIndex = 2*index;
			tryIndex = 0;
			if (dIndex <= numElem)
			{
				if (dIndex+1 <= numElem)
				{
					if (comp(v[dIndex], v[dIndex+1]))
						tryIndex = dIndex;
					else
						tryIndex = dIndex+1;
				}
				else
					tryIndex = dIndex;
			}

			if ((tryIndex != 0) && comp(v[tryIndex], v[index]))
			{
				swap(index, tryIndex);
				index = tryIndex;
			}
			else
				tryIndex = 0;
		}
	}
	//	parameter /index/ is indexing v, it's not a key
	bool remove(int index)
	{
		if (index > numElem)
			return 1;
		swap(index, numElem--);
		keyToHeap[heapToKey[numElem+1]] = -1;
		heapToKey[numElem+1] = -1;
		if (comp(v[index], v[numElem+1]))
			tryUp(index);
		else
			tryDown(index);
		return 0;
	}
	//	parameter /index/ is indexing v, it's not a key
	bool updateElement(int index, const type &newX)
	{
		if (index > numElem)
			return 1;
		type oldValue = v[index];
		v[index] = newX;
		if (comp(oldValue, newX))
			tryDown(index);
		else
			tryUp(index);
		return 0;
	}
};

#define fileIn "dijkstra.in"
#define fileOut "dijkstra.out"

int cost[50001];
bool visited[50001];
std::vector<int> target[50001];
std::vector<int> costEdge[50001];
int main()
{
	std::ifstream sIn(fileIn);
	std::ofstream sOut(fileOut);


	int n, m;
    int x, y, c;
 
    int i, currCost, currNode;
	Heap<int> heap(50000, true);
 
    sIn >> n >> m;
	
	for ( i = 1; i <= n; ++i )
	{
		visited[i] = 0;
		cost[i] = 0;
	}
    for ( i = 1; i <= m; ++i )
    {
        sIn >> x >> y >> c;
 
        target[x].push_back(y);
        costEdge[x].push_back(c);
    }
 
	heap.push(0, 1);	//	pushing the starting node; defaults to 1
 
	while ( !heap.isEmpty() )
    {
		heap.pop(&currCost, &currNode);
		visited[currNode] = 1;
		cost[currNode] = currCost;

		for (int i = 0; i < (int)target[currNode].size(); ++i)
			if (!visited[target[currNode][i]])
				if (heap.getValueAtKey(&c, target[currNode][i]))	//	if true, element is not in the heap yet
					heap.push(currCost + costEdge[currNode][i], target[currNode][i]);
				else
					if (c > currCost + costEdge[currNode][i])	//	updating cost if less than the current one for the neighbouring node
						heap.updateElementByKey(currCost + costEdge[currNode][i], target[currNode][i]);
    }
 
    for ( i = 2; i <= n; ++i )
        sOut << cost[i] << ' ';
    sOut << '\n';


	/*
	Heap<int> heap(200000, 1);
	int n, i;
	int p, x;

	sIn >> n;
	int added = 0;
	for (i = 0; i < n; ++i)
	{
		sIn >> p;
		switch (p)
		{
			case 1:
			{
				sIn >> x;
				heap.push(x, ++added);
				break;
			}
			case 2:
			{
				sIn >> x;
				heap.removeByKey(x);
				break;
			}
			case 3:
			{
				int minValue;
				heap.pop(&minValue, NULL, false);
				sOut << minValue << '\n';
				break;
			}
			default:
			{
				//	??? invalid input
			}
		}
	}
	*/

	return 0;
}