#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <bitset>

using namespace std;

class InParser {

	private:
		
		static const int buffSZ = (1 << 15);
		ifstream File;
		int buffPos;
		char buff[buffSZ];

		void _advance() {

			if (++buffPos == buffSZ) {

				File.read(buff, buffSZ);
				buffPos = 0;
			}
		}

	public:
			
		InParser(const char *FileName) {

			buffPos = buffSZ - 1;
			File.open(FileName);
		}

		InParser& operator >>(int &no) {

			while (!isdigit(buff[buffPos]))
				_advance();
			no = 0;
			while (isdigit(buff[buffPos])) {

				no = no * 10 + buff[buffPos] - '0';
				_advance();
			}
			return *this;
		}
};

class OutParser {

	private:
		
		static const int buffSZ = (1 << 15);
		ofstream File;
		char buff[buffSZ];
		int buffPos;
		vector <int> digits;

		void _advance() {

			if (++buffPos == buffSZ) {

				File.write(buff, buffSZ);
				buffPos = 0;
			}
		}

		void printChar(char no) {

			buff[buffPos] = no;
			_advance();
		}

	public:
		
		OutParser(const char *FileName) {

			File.open(FileName);
			digits.resize(11);
			buffPos = 0;
		}

		~OutParser(){
			
			File.write(buff, buffSZ);
			buffPos = 0;
		}

		OutParser& operator <<(char ch) {

			printChar(ch);
			return *this;
		}

		OutParser& operator <<(int no) {

			int idx = 0;

			if (no == 0)
				digits[++idx] = 0;

			while (no) {

				digits[++idx] = no % 10;
				no /= 10;
			}

			for (; idx; --idx)
				printChar(digits[idx] + '0');

			return *this;
		}
};

InParser fin("dijkstra.in");
OutParser fout("dijkstra.out");

const int maxNodesCnt = 5e4 + 5, Inf = INT_MAX;

class weightedGraph {

	public:
		int adjNode, cost;
};

list <weightedGraph> adjList[maxNodesCnt];
vector <int> dist;
int nodesCnt, edgesCnt;

void readData() {

	fin >> nodesCnt >> edgesCnt;

	for (; edgesCnt; --edgesCnt) {

		int from, to, cost;
		fin >> from >> to >> cost;
		adjList[from].push_back({to, cost});
	}
}
class heapKey {

	public:
		int node, cost;

		bool operator <(const heapKey &other) const{

			return this -> cost > other.cost;
		}
};

void dijkstra(int node) {

	dist.resize(nodesCnt + 1);
	fill(dist.begin(), dist.end(), Inf);

	dist[node] = 0;

	priority_queue <heapKey, vector <heapKey> > Heap;
	Heap.push({node, dist[node]});

	bitset <maxNodesCnt> inHeap;
	

	while (!Heap.empty()) {

		int currNode = Heap.top().node;
		Heap.pop();
		inHeap[currNode] = false;

		for (const weightedGraph &New : adjList[currNode]) {

			int adjNode = New.adjNode;
			int cost = New.cost;

			if (dist[adjNode] > dist[currNode] + cost) {

				dist[adjNode] = dist[currNode] + cost;

				if (!inHeap[adjNode]) {

					Heap.push({ adjNode, dist[adjNode] });
					inHeap[adjNode] = true;
				}
			}
		}
	}
}

int main() {

	readData();
	dijkstra(1);

	for (int node = 2; node <= nodesCnt; ++node) {

		if (dist[node] == Inf)
			dist[node] = 0;
		fout << dist[node] << ' ';
	}
}