#include<iostream>
#include<fstream>
#include<vector>

using namespace std;
ifstream fin("input");

namespace dsl {
    template<class type>

    class heap {
    private:
        std::vector<type> data;
        unsigned count;

        /* Returns the index of the left son of the node */
        unsigned left_son(unsigned node) {
            return node << 1u;
        }

        /* Returns the index of the right son of the node */
        unsigned right_son(unsigned node) {
            return (node << 1u) + 1;
        }

        /* Returns the index of the father of the node */
        unsigned father(unsigned node) {
            return node >> 1u;
        }

        /* This method shifts the node down the tree, comparing its value with the value of its children */
        void shift(unsigned node) {
            unsigned best = 0, l = left_son(node), r = right_son(node);

            /* Check if the node is not a leaf node*/
            if (l <= count) {

                best = l;

                /* If it also has a right-node then we have to take the child node with the maximum value */

                if (r <= count) {
                    best = (data[l] > data[r]) ? l : r;
                }

                /* If the value of the best child node is greater than the value of this node, we swap the
                 * two nodes and continue the process*/

                if (data[best] > data[node]) {
                    std::swap(data[node], data[best]);
                    shift(best);
                }
            }
        }

        /* This method lifts the node up the tree, comparing its value with the value of its father */
        void percolate(unsigned node) {
            unsigned ft = father(node);

            /* If this is not the root node and its value is greater than the value of its parent,
             * swap the two values and continue the process */

            if (ft != 0 && data[node] > data[ft]) {
                std::swap(data[node], data[ft]);
                percolate(ft);
            }
        }


    public:
        heap() : data(1), count(0) {

        }

        /* Constructs a heap from a container. First and last are iterators to the given container.
         * This method first inserts its contents and then sorts the heap */

        template<class Iter>
        heap(Iter first, Iter last) {
            data.resize(1);
            data.insert(data.begin() + 1, first, last);

            count = data.size() - 1;

            /* Now we build the heap */
            for (unsigned node = count / 2; node >= 1; node--) {
                shift(node);
            }
        }

        /* This method returns the size of the heap */
        unsigned size() {
            return count;
        }

        /* This method is used to check if the heap is empty*/
        bool empty() {
            return count == 0;
        }

        /* This method adds a new value into the heap */
        void push(type value) {
            data.push_back(value);
            count++;
            percolate(count);
        }

        /* This method removes the root of the heap */
        void pop() {
            std::swap(data[1], data[count]);
            data.pop_back();
            count--;
            shift(1);
        }

        /* This method returns the value of the root */
        type top() {
            return data[1];
        }

    };
}

const int mx=60000;
const long long inf=2e18;;

struct edge{
	int dest,cost;
};

struct node{
	int index;
	long long cost;
	bool operator>(const node&other){
		return cost<other.cost;
	}
};

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector<edge> g[mx];
int n,m;
long long res[mx];

void read(){
	in>>n>>m;
	int a,b,c;
	for(int i=0;i<m;i++){
		in>>a>>b>>c;
		g[a].push_back({b,c});
	}
}

void solve(){
	dsl::heap<node> q;

	for(int i=1;i<=n;i++)
		res[i]=inf;
	
	res[1]=0;
	q.push({1,0});
	while(q.size()){
		node here=q.top();
		q.pop();

		if(here.cost>res[here.index])
			continue;
		for(edge k:g[here.index]){
			if(res[k.dest]>here.cost+k.cost){
				res[k.dest]=here.cost+k.cost;
				q.push({k.dest,res[k.dest]});
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(res[i]==inf)
			res[i]=0;
		out<<res[i]<<" ";
	}
}



int main(){
	read();
	solve();
	return 0;
}