#include <bits/stdc++.h> 

const int kNmax = 100005;

struct Edge {
	int x;
	int y;
};

class Task {
 public:
	void solve() {
		read_input();
        get_result();
	}

 private:
	int n;
	int m;
	std::vector<int> adj[kNmax];
    std::map<std::pair<int, int>, int> costs;
   
	void read_input() {
		std::ifstream fin("dijkstra.in");
		fin >> n >> m;
		for (int i = 1, x, y, cost; i <= m; i++) {
			fin >> x >> y >> cost;
			adj[x].push_back(y);
            std:: pair<int, int> key = std::pair<int, int>(x, y);
            costs[key] = cost;
        }

		fin.close();
	}

	void get_result() {
        std::vector<int> distances(n + 1, INT_MAX); 
        std::priority_queue <std::pair<int, int>, std::vector<std::pair<int, int>>, 
            std::greater<std::pair<int, int>>> pq;
        std::pair<int, int> elem(1, 0);
        pq.push(elem);
        distances[1] = 0; 

        while (!pq.empty()) { 
            int node = pq.top().first;
            pq.pop();
           
            for (auto& adj : adj[node]) {
                std::pair<int, int> key = std::pair<int, int>(node, adj);
                if (distances[adj] > distances[node] + costs[key]) { 
                    distances[adj] = distances[node] + costs[key];
                    std::pair<int, int> newElem(adj, distances[adj]);
                    pq.push(newElem);
                } 
            } 
        }

        std::ofstream fout("dijkstra.out");
		for (int i = 2; i <= n; i++) {
            if (distances[i] == INT_MAX) {
                fout << "0 ";
            } else {
                fout << distances[i] << " ";
            }
        }
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}