#include <fstream>
#include <vector>

#define Nmax 50100
#define oo (1 << 30)
#define neighbour Graph[node][i].first
#define cost Graph[node][i].second

using namespace std;

class priorityQueue {

    #define root 1
    #define father (node >> 1)
    #define leftSon (node << 1)
    #define rightSon ((node << 1) | 1)
    #define compare(a, b) (A[Heap[a]] < A[Heap[b]])

    private:
        int size, Heap[Nmax], Location[Nmax], A[Nmax];

    public:
        priorityQueue() {
            size = 0;
        }

        void insert(int index, int value) {
            A[index] = value;
            Heap[++size] = index;
            Location[index] = size;

            up(size);
        }

        void update(int index, int value) {
            A[index] = value;
            up(Location[index]);
        }

        void pop() {
            Heap[1] = Heap[size--];
            Location[Heap[1]] = 1;
            down(1);
        }

        inline int distance(int index) {
            return A[index];
        }

        int front() {
            return Heap[1];
        }

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

    private:
        void up(int node) {

            while(node != root && compare(node, father)) {
                swap(Heap[node], Heap[father]);
                swap(Location[Heap[node]], Location[Heap[father]]);
                node = father;
            }
        }

        void down(int node) {

            int son;
            do {
                son = 0;

                if(leftSon <= size) {
                    son = leftSon;

                    if(rightSon <= size && compare(rightSon, son))
                        son = rightSon;

                    if(compare(node, son))
                        son = 0;
                }

                if(son != 0) {
                    swap(Heap[node], Heap[son]);
                    swap(Location[Heap[node]], Location[Heap[son]]);
                    node = son;
                }
            } while(son);
        }
};

vector < pair<int, int> > Graph[Nmax];
priorityQueue pq;
int N;

void Dijkstra() {

    int i, node;

    pq.insert(1, 0);
    for(i = 2; i <= N; i++)
        pq.insert(i, oo);

    while(!pq.empty()) {

        node = pq.front();
        pq.pop();

        for(i = 0; i < Graph[node].size(); i++)
            if(pq.distance(node) + cost < pq.distance(neighbour))
                pq.update(neighbour, pq.distance(node) + cost);
        }

}
void Read() {

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

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

    in.close();
}
void Write() {

    ofstream out("dijkstra.out");

    for(int i = 2; i <= N; i++)
        out << pq.distance(i) << ' ';

    out << '\n';
    out.close();
}
int main() {

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

    return 0;
}