#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>

#define FAST cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
ifstream fin("input");


void init(){
	FAST
#ifndef ONLINE_JUDGE
		cin.rdbuf(fin.rdbuf());
#endif
}

namespace dsl {
    template<class type>
    class heap {
    private:
        std::vector<type> data;

        void shift(unsigned node);

        void percolate(unsigned node);

        unsigned count;

    public:
        template<class Iter>
        void build(Iter first,Iter last);//builds the heap from a container

        void push(type value);

        void pop();

        void clear();

        type top() const; //returns the minimum element

        unsigned size() const;

        bool empty() const;

        heap();
    };


    inline unsigned father(unsigned node) {
        return node >> 1u;
    }

    inline unsigned left(unsigned node) {
        return node << 1u;
    }

    inline unsigned right(unsigned node) {
        return (node << 1u) + 1;
    }

    template <class type>
    inline unsigned int heap<type>::size() const {
        return count;
    }

    template<class type>
    inline heap<type>::heap():count(0),data(1) {

    }

    template<class type>
    inline type heap<type>::top() const {
        return data[1];
    }

    template<class type>
    inline void heap<type>::percolate(unsigned int node) {
        unsigned f=father(node);
        if(f>0 && data[node]>data[f]){
            std::swap(data[f],data[node]);
            percolate(f);
        }
    }

    template <class type>
    inline void heap<type>::push(type value) {
        data.push_back(value);
        count++;
        percolate(count);
    }

    template<class type>
    inline void heap<type>::shift(unsigned int node) {
        unsigned l = left(node), r = right(node);

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

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

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

    template<class type>
    template<class Iter>
    inline void heap<type>::build(Iter first,Iter last) {
        data.resize(1);
        data.insert(data.end(),first,last);
        count=data.size()-1;

        for (unsigned i = count/2; i >= 1; i--) {
            shift(i);
        }
    }

    template<class type>
    inline void heap<type>::clear() {
        data.resize(1);
        count=0;
    }

    template<class type>
    inline void heap<type>::pop() {
        data[1]=data[count];
        data.pop_back();
        count--;
        shift(1);
    }

    template <class type>
    inline bool heap<type>::empty() const {
        return count==0;
    }
}

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int mx=60000;
const long long inf=2e18;
struct edge{
	int destination;
	long long cost;
};
struct node{
	int index;
	long long cost;
	bool operator >(const node&other){
		return cost<other.cost;
	}
};

int n,m;
long long result[mx];
vector<edge> g[mx];


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

void solve(){
	dsl::heap<node> q;
	q.push({0,0});
	result[0]=0;
	while(!q.empty()){
		node here=q.top();
		q.pop();

		if(result[here.index]<here.cost)
			continue;

		result[here.index]=here.cost;

		for(edge k:g[here.index]){
			int next=k.destination;
			long long newcost=k.cost+here.cost;
			if(newcost<result[next]){
				q.push({next,newcost});
			}
		}
	}

	for(int i=1;i<n;i++){
		if(result[i]==inf)
			out<<0<<" ";
		else out<<result[i]<<" ";
	}
}


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