/*



*/

#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

const int NMAX=5e4+8;
int n,m;
std::vector<std::pair<int,int> > g[NMAX];
int dist[NMAX];

class Heap {
private:

    struct nodd {
        int nod;
        int dist;
        nodd() : nod(0), dist(0) {}
        nodd(int nod,int dist) : nod(nod), dist(dist) {}
    };

    std::vector<nodd> h;
    std::vector<int> pos;
    int n;

    void sch(int pos1,int pos2) {
        pos[h[pos1].nod]=pos2;
        pos[h[pos2].nod]=pos1;
        std::swap(h[pos1],h[pos2]);
    }

    void move_up(int idx) {
        while(idx>0 && h[idx].dist<h[(idx-1)/2].dist) {
            sch(idx,(idx-1)/2);
            idx=(idx-1)/2;
        }
    }

    void move_down(int idx) {
        int st=2*idx+1;
        int dr=2*idx+2;
        int idx_mn=-1,mn=h[idx].dist;

        if(st<(int)h.size() && h[st].dist<mn) {
            mn=h[st].dist;
            idx_mn=st;
        }

        if(dr<(int)h.size() && h[dr].dist<mn) {
            mn=h[dr].dist;
            idx_mn=dr;
        }

        if(idx_mn!=-1) {
            sch(idx,idx_mn);
            move_down(idx_mn);
        }
    }

public:

    Heap(int n) : n(n) {
        pos=std::vector<int>(n+1,-1);
    }

    std::pair<int,int> top() {
        return {h[0].nod,h[0].dist};
    }

    void insert(int nod,int dist) { // aici e incorporata si functia de decrease
        if(pos[nod]>-1) {
            if(dist<h[pos[nod]].dist) {
                h[pos[nod]].dist=dist;
                move_up(pos[nod]);
            }
        }
        else {
            h.push_back({nod,dist});
            pos[nod]=(int)h.size()-1;
            move_up(pos[nod]);
        }
    }

    void pop() {
        pos[h[0].nod]=-1;
        h[0]=h.back();
        h.pop_back();

        if(!h.empty()) {
            pos[h[0].nod]=-1;
            move_down(0);
        }
    }

    bool empty() {
        return h.empty();
    }
};

void dijk(int s) {
    Heap q(n);

    for(int i=1; i<=n; i++) {
        dist[i]=INT_MAX;
    }
    dist[s]=0;

    q.insert(s,0);
    while(!q.empty()) {
        int nod=q.top().first;
        q.pop();

        for(const auto &[vec,w]:g[nod]) {
            if(dist[vec]>dist[nod]+w) {
                dist[vec]=dist[nod]+w;
                q.insert(vec,dist[vec]);
            }
        }
    }
}

int main() {
    std::ifstream fin("dijkstra.in");
    std::ofstream fout("dijkstra.out");

    fin >> n >> m;
    for(int i=1; i<=m; i++) {
        int x,y,w;
        fin >> x >> y >> w;
        g[x].push_back({y,w});
    }

    dijk(1);

    for(int i=2; i<=n; i++) {
        if(dist[i]==INT_MAX)
            fout << 0 << " ";
        else 
            fout << dist[i] << " ";
    }

    return 0;
}