#include <fstream>
#include <vector>
#include <algorithm>

#define Nmax 50100
#define oo (1 << 30)
#define Neighbour Graph[Node][i].first
#define Cost Graph[Node][i].second

using namespace std;

bool compare(pair<int, int> A, pair<int, int> B) {
	return A.first < B.first;
}

template <typename T>
class priorityQueue {

    #define root 1
    #define father(x) (x >> 1)
    #define leftSon(x) (x << 1)
    #define rightSon(x) ((x << 1) | 1)
    #define compare(a, b) (H[a - 1].second < H[b - 1].second)
    #define change(a, b) swap(H[a - 1], H[b - 1])

    private:
        vector <T> H;

    public:
        void insert(T Value) {
            H.push_back(Value);
            up(H.size());
            }

        void pop() {
            H[0] = H[H.size() - 1];
            H.pop_back();
            down(root);
            }

	int distance(int Node) {
		return H[Node - 1].second;
	}

        int front() {
            return H[0].first;
            }

        bool empty() {
            return (H.size() == 0);
            }

	void sorts() {

		sort(H.begin(), H.end(), compare);

	}

    private:
        void up(int Node) {

            while(Node != root && compare(Node, father(Node))) {
                change(Node, father(Node));
                Node = father(Node);
                }

            }

        void down(int Node) {

            int son;

            do {
                son = 0;

                if(leftSon(Node) <= H.size()) {
                    son = leftSon(Node);
                    if(rightSon(Node) <= H.size() && compare(rightSon(Node), son))
                        son = rightSon(Node);
                    }

                if(compare(Node, son))
                    son = 0;

                if(son != 0) {
                    change(Node, son);
                    Node = son;
                    }
            } while(son);

            }
};

vector < pair<int, int> > Graph[Nmax];
priorityQueue < pair<int, int> > Heap;
int N, Distance[Nmax];
bool used[Nmax];

void Dijkstra() {

    int i, Node;

    Heap.insert(make_pair(1, 0));

    for(i = 2; i <= N; i++)
    	Heap.insert(make_pair(i, oo));

    while(!Heap.empty()) {

        Node = Heap.front();
        Heap.pop();

	if(used[Node])
		continue;
	else
		used[Node] = true;

        for(i = 0; i < Graph[Node].size(); i++) {

            if(Heap.distance(Neighbour) > Heap.distance(Node) + Cost)
                Heap.insert(make_pair(Neighbour, Heap.distance(Node) + Cost));

            }

    }

}
void Read() {

    int x, y, cost, M;
    ifstream in("dijkstra.in");

    in >> N >> M;

    while(M--) {
        in >> x >> y >> cost;
        Graph[x].push_back(make_pair(y, cost));
        }

    in.close();

}
void Write() {

    ofstream out("dijkstra.out");

	Heap.sorts();

    for(int i = 2; i <= N; i++)
        out << (Heap.distance(i) != oo ? Heap.distance(i) : 0) << ' ';

    out << '\n';
    out.close();

}
int main() {

    Read();
    Dijkstra();
    Write();

    return 0;

}