#include <bits/stdc++.h> 

const int kNmax = 50009;

struct Edge {
	int x;
	int y;
};

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

 private:
	int n;
	int m;
	std::vector<std::pair<int, int>> adj[kNmax];
    std::vector<int> distances;
    std::priority_queue <std::pair<int, int>, std::vector<std::pair<int, int>>, 
            std::greater<std::pair<int, int>>> pq;
    std::vector<int> parent;
   
	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(std::pair<int, int>(cost, y));
        }

		fin.close();
	}

	void get_result() {
        distances = std::vector<int>(n + 1, INT_MAX); 
        parent = std::vector<int>(n + 1, -1);

        std::pair<int, int> elem(0, 1);
        pq.push(elem);
        distances[1] = 0;
        parent[1] = 0;

        while (!pq.empty()) { 
            auto aux = pq.top();
            int node = aux.second;
            int c = aux.first;
            pq.pop();

            if (c > distances[node]) {
                continue;
            }
           
            for (auto& it : adj[node]) {
                int adj = it.second;
                int cost = it.first;
                
                if (distances[adj] > distances[node] + cost) { 
                    distances[adj] = distances[node] + cost;
                    std::pair<int, int> newElem(distances[adj], adj);
                    parent[adj] = node;
                    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 << "\n";
		fout.close();
	}

    void getAllPaths() {
        for (int i = 1; i <= n; i++) {
            std::vector<int> aux = getPath(i);
            for (auto& node : aux) {
                std::cout << node << " ";
            }
            std::cout << "\n";
        }
    }

    std::vector<int> getPath(int node) {
        std::vector<int> path;
        if (parent[node] == -1) {
            return path;
        }
	
        while (node != 0) {
            path.push_back(node);
            node = parent[node];
        }
	
        reverse(path.begin(), path.end());
        return path;
    }
};

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