#include <iostream>
#include <vector>
#include <climits>
#include<unordered_map>
#include <algorithm>
#include <set>
#include<string>
#include<map>
#include<queue>
#include<cmath>
#include<fstream>
#include<list>
#include<iomanip>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define ll long long
typedef pair<ll, ll> iPair;

class Graph {
	ll V;
	list<iPair>* adj;
public:
	Graph(ll V) {
		this->V = V;
		adj = new list<iPair>[V];
	}

	void addEdge(ll u, ll v, ll w) {
		adj[u].push_back({ v, w });
	}

	void shortestPath(ll src) {
		priority_queue <iPair, vector<iPair>, greater<iPair>>pq;
		vector<ll>dist(this->V, LLONG_MAX);
		pq.push({0, src});
		dist[src] = 0;
		while (!pq.empty()) {
			ll u = pq.top().second;
			pq.pop();
			list<iPair>::iterator i;
			for (i = adj[u].begin(); i != adj[u].end(); i++) {
				ll v = (*i).first;
				ll weight = (*i).second;
				if (dist[v] > dist[u] + weight) {
					dist[v] = dist[u] + weight;
					pq.push({ dist[v], v });
				}
			}
		}
		for (int i = 1; i < V; i++) {
			if (dist[i] == LLONG_MAX)dist[i] = 0;
			out << dist[i] << " ";
		}
	}
};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n, m;
	in >> n >> m;
	Graph g(n);
	while (m--) {
		ll u, v, w;
		in >> u >> v >> w;
		g.addEdge(u-1, v-1, w);
	}
	g.shortestPath(0);
}