#include <fstream>
#include <queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax=50000, inf=2e9;
int d[nmax+1];

struct str {
    int x, y;
};
vector <str> g[nmax+1];

struct cmp {
    bool operator () (const str &x, const str &y) {
        return x.y<y.y;
    }
};

priority_queue <str, vector<str>, cmp> h;

int main () {
    int n, m;
    fin>>n>>m;

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

    for (int i=2; i<=n; i++) {
        d[i]=inf;
    }

    str aux;
    aux.x=1;
    aux.y=0;
    h.push(aux);

    while (h.empty()==0) {
        int x=h.top().x, y=h.top().y;
        h.pop();
        if (y==d[x]) {
            for (int i=0; i<int(g[x].size()); i++) {
                int xn=g[x][i].x, yn=g[x][i].y;
                if (d[xn]>d[x]+yn) {
                    d[xn]=d[x]+yn;
                    aux.x=xn;
                    aux.y=d[xn];
                    h.push(aux);
                }
            }
        }
    }

    for (int i=2; i<=n; i++)  {
        if (d[i]==inf) {
            fout<<"0 ";
        } else {
            fout<<d[i]<<" ";
        }
    }
    fout<<"\n";
    return 0;
}