#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] != oo ? H.Distance[i] : 0) << ' ';
 
    out << '\n';
    out.close();
 
}
int main() {
 
    Read();
    Dijkstra();
    Write();
 
    return 0;
 
}