#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 HEAP {

    #define Root 1
    #define Father (Node >> 1)
    #define leftSon (Node << 1)
    #define rightSon ((Node << 1) | 1)
    #define compare(a, b) (Distance[Heap[a]] < Distance[Heap[b]])

    private:
        int top, Heap[Nmax], Position[Nmax];

    public:
        int Distance[Nmax];

    public:

        HEAP() {

            top = 0;

        }

        void insert(int X, int Value) {

            Distance[X] = Value;
            Heap[++top] = X;
            Position[X] = top;

            up(top);

        }

        void update(int X, int Value) {

            Distance[X] = Value;
            up(Position[X]);

        }

        void pop() {

            Heap[1] = Heap[top--];
            Position[Heap[1]] = 1;
            down(1);

        }

        int front() {

            return Heap[1];

        }

        int size() {

            return top;

        }

        bool empty() {

            return (top == 0);

        }

    private:

        void up(int Node) {

            while(Node != Root && compare(Node, Father)) {
                swap(Heap[Node], Heap[Father]);
                swap(Position[Heap[Node]], Position[Heap[Father]]);
                Node = Father;
                }

        }

        void down(int Node) {

            int Son;

            do {

                Son = 0;

                if(leftSon <= size()) {

                    Son = leftSon;
                    if(rightSon <= size() && compare(rightSon, leftSon))
                        Son = rightSon;

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

                    }

                if(Son != 0) {
                    swap(Heap[Node], Heap[Son]);
                    swap(Position[Heap[Node]], Position[Heap[Son]]);
                    Node = Son;
                    }

            } while(Son != 0);

        }

};

vector < pair<int, int> > Graph[Nmax];
HEAP H;
int N, Distance[Nmax];

void Dijkstra() {

    int i, Node;

    H.insert(1, 0);

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

    while(!H.empty()) {

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

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

            if(H.Distance[Neighbour] > H.Distance[Node] + Cost)
                H.update(Neighbour, H.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");

    for(int i = 2; i <= N; i++)
        out << H.Distance[i] << ' ';

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

}
int main() {

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

    return 0;

}