#include <bits/stdc++.h>

using namespace std ;

class Reader {
public:
    Reader() {}
    Reader(const char *file_name) {
        input_file.open(file_name,std::ios::in | std::ios::binary);
        input_file.sync_with_stdio(false);
        index&=0;
        input_file.read(buffer,SIZE); }
    inline Reader &operator >>(int &n) {
        for (; buffer[index]<'0' or buffer[index]>'9'; inc());
        n&=0;
        sign&=0;
        sign|=(buffer[index-1]=='-');
        for (; '0'<=buffer[index] and buffer[index]<='9'; inc())
            n=(n<<1)+(n<<3)+buffer[index]-'0';
        n^=((n^-n)&-sign);
        return *this; }
    ~Reader() {
        input_file.close(); }
private:
    std::fstream input_file;
    static const int SIZE=1<<17;
    char buffer[SIZE];
    int index,sign;
    inline void inc() {
        if(++index==SIZE)
            index=0,input_file.read(buffer,SIZE); } };

Reader f ("dijkstra.in") ;
ofstream g ("dijkstra.out") ;

void Read(int &N,int &M,vector < vector <pair <int, int> > > &G) {
    f >> N >> M ;
    for(int i=1; i<=M; i++) {
        int x, y, cost ;
        f >> x >> y >> cost ;
        G [x].push_back ({y, cost }) ; } }

vector<int> Dijkstra(int N,vector < vector <pair <int, int> > > &G,int startPoint) {
    auto comp = [](pair <int, int> A, pair <int, int> B) {
        return A.second > B.second ; };
    priority_queue < pair <int, int>, vector < pair <int, int> >, decltype (comp)> PQ (comp) ;
    vector <int> D (N + 1, INT_MAX) ;
    D [startPoint] = 0 ;
    PQ.push({startPoint, 0 }) ;
    while (!PQ.empty()) {
        auto current = PQ.top () ;
        PQ.pop () ;
        if (D [current.first] != current.second) continue ;
        for (auto next: G [current.first]) {
            if (D [next.first] > D [current.first] + next.second) {
                D [next.first] = D [current.first] + next.second ;
                PQ.push ({next.first, D [next.first] }) ; } } }
    return D; }

void Write(vector <int> D) {
    for (int i = 2 ; i < D.size() ; ++ i)
        g << ((D [i] >= INT_MAX) ? 0 : D [i]) << ' ' ; }

int main() {
    int N, M;
    vector < vector <pair <int, int> > > G (50001) ;
    Read(N,M,G);
    Write(Dijkstra(N,G,1)); }