#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
#include <set>
#include <queue>
#include <stack>

#define Inf ((1<<30)-1)

using namespace std;

struct Graph {
	vector<list<pair<unsigned int, int> > > v;
};

struct SimpleGraph {
	vector<list<unsigned int> > v;
};

template <typename Type>
class minHeap {
	vector<Type> v;
public:
	void swap(unsigned int pos1, unsigned int pos2) {
		Type aux = v[pos1];
		v[pos1] = v[pos2];
		v[pos2] = aux;
	}

	void push(Type x) {
		if (v.empty())
			v.push_back(x);

		v.push_back(x);

		int pos = v.size() - 1;

		while (pos > 1 && v[pos] < v[pos / 2]) {
			swap(pos, pos / 2);

			pos /= 2;
		}
	}

	void pop() {
		if (empty())
			return;
		swap(1, v.size() - 1);
		v.pop_back();

		bool okay = true;
		unsigned int pos = v.size() - 1;

		if (empty())
			return;

		while (okay) {
			okay = false;

			if (2 * pos + 1 == v.size()) {
				if (v[pos] > v[pos * 2])
					swap(pos, pos * 2),
					pos = 2 * pos;
				okay = true;
			}
			else
				if (2 * pos + 1 < v.size()) {
					if (v[pos] > v[2 * pos] || v[pos] > v[2 * pos + 1])
						if (v[2 * pos] < v[2 * pos + 1])
							swap(pos, 2 * pos),
							pos = 2 * pos;
						else
							swap(pos, 2 * pos + 1),
							pos = 2 * pos + 1;
					okay = true;
				}

		}
	}

	Type top() {
		return v[1 - (v.size() == 1)];
	}

	bool empty() {
		return v.size() <= 1;
	}
};

Graph* readOrientedGraph() {
	int n, m;
	cin >> n >> m;

	Graph *G = new Graph();
	G->v.assign(n+1, *new list<pair<unsigned int, int> >());

	unsigned int x, y;
	int z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		G->v[x].push_back(make_pair(y, z));
	}

	return G;
}

Graph* readGraph() {
	int n, m;
	cin >> n >> m;

	Graph *G = new Graph();
	G->v.assign(n + 1, *new list<pair<unsigned int, int> >());

	unsigned int x, y;
	int z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		G->v[x].push_back(make_pair(y, z));
		G->v[y].push_back(make_pair(x, z));
	}

	return G;
}

SimpleGraph* readSimpleOrientedGraph() {
	int n, m;
	cin >> n >> m;

	SimpleGraph *G = new SimpleGraph();
	G->v.assign(n + 1, *new list<unsigned int>());

	unsigned int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		G->v[x].push_back(y);
		G->v[y].push_back(x);
	}

	return G;
}

int *d;

void dijkstra(Graph *G, unsigned int startNode) {
	minHeap<pair<int, unsigned int> > st;
	d = new int[G->v.size ()];
	for (unsigned int i = 1; i < G->v.size(); i++)
		d[i] = i == startNode ? 0 : Inf;

	st.push(make_pair (0, startNode));
	while (!st.empty()) {
		unsigned int node = st.top ().second;
		//pop
		st.pop();

		for (list<pair<unsigned int, int> >::iterator it = G->v[node].begin (); it != G->v[node].end (); it++)
			if (d[it->first] > d[node] + it->second) {				
				d[it->first] = d[node] + it->second;
				//push
				st.push(make_pair (d[it->first], it->first));
			}
	}
}


bool *isInQ;
unsigned int *cnt;
bool bellman_ford(Graph *G, int startNode) {
	queue<unsigned int> q;

	d = new int[G->v.size()];
	isInQ = new bool[G->v.size()];
	cnt = new unsigned int[G->v.size()];

	for (unsigned int i = 1; i < G->v.size(); i++)
		d[i] = i == startNode ? 0 : Inf,
		isInQ[i] = false,
		cnt[i] = 0;

	q.push(startNode);
	isInQ[startNode] = true;

	while (!q.empty ()) {
		unsigned int node = q.front();
		q.pop();
		isInQ[node] = false;

		for (list<pair<unsigned int, int> >::iterator it = G->v[node].begin(); it != G->v[node].end(); it++)
			if (d[it->first] > d[node] + it->second) {
				d[it->first] = d[node] + it->second;

				if (!isInQ[it->first]) {
					isInQ[it->first] = true;

					cnt[it->first]++;
					if (cnt[it->first] > G->v.size() - 1)
						return false;
					q.push(it->first);
				}
			}
	}
	
	return true;
}

void euler(SimpleGraph G, unsigned int node, vector<unsigned int> &eulerCycle) {
	stack<int> st;
	st.push(node);
	while (!st.empty()) {
		node = st.top ();
		for (list<unsigned int>::iterator it = G.v[node].begin(); it != G.v[node].end(); it++) {
			unsigned int nextNode = *it;
			G.v[node].erase(it);
			for (list<unsigned int>::iterator nit = G.v[nextNode].begin(); nit != G.v[nextNode].end(); nit++)
				if (node == *nit) {
					G.v[nextNode].erase(nit);
					break;
				}

			st.push(node);
		}

		eulerCycle.push_back(node);
		st.pop();
	}
}

bool *viz;

bool dfs(SimpleGraph *G, int node, unsigned int &visitedNodesCount) {
	visitedNodesCount++;
	viz[node] = true;

	if (G->v[node].size () % 2)
		return false;

	for (list<unsigned int>::iterator it = G->v[node].begin(); it != G->v[node].end(); it++)
		if (!viz[*it])
			if (!dfs(G, *it, visitedNodesCount))
				return false;

	return true;
}

bool hasEurelianCycle(SimpleGraph *G) {
	unsigned int visitedNodesCount = 0;
	viz = new bool[G->v.size()];

	if (dfs(G, 1, visitedNodesCount) && visitedNodesCount == G->v.size() - 1) {
		vector<unsigned int> cycle;

		euler(*G, 1, cycle);
	}
	
	

	return true;
}

void bellman_fordProblem() {
	freopen("bellmanford.in", "rt", stdin);
	freopen("bellmanford.out", "wt", stdout);

	unsigned int startingNode = 1;
	Graph *G = readOrientedGraph();

	if (bellman_ford(G, startingNode)) {
		for (unsigned int i = 1; i <= G->v.size() - 1; i++)
			if (i != startingNode)
				cout << (Inf != d[i] ? d[i] : 0) << ' ';
	}
	else
		cout << "Ciclu negativ!";
}

void eulerProblem() {
	freopen("euler.in", "rt", stdin);
	freopen("euler.out", "wt", stdout);

	SimpleGraph *G = readSimpleOrientedGraph();
}

void dijkstraProblem() {
	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);

	unsigned int startingNode = 1;
	Graph *G = readOrientedGraph();

	dijkstra(G, startingNode);
	for (unsigned int i = 1; i <= G->v.size() - 1; i++)
		if (i != startingNode)
			cout << (Inf != d[i] ? d[i] : 0) << ' ';
}

int main() {
	dijkstraProblem();
}