#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

FILE *re, *we;

const int MAXN = 50001;
const int MARE = 2000000004;
struct edge
{
    const bool operator < (const edge &gigi)const {
        return co > gigi.co;
    }
    int la, co;
};

vector <edge> gf[MAXN];
priority_queue <edge> hdj;
int n, m, d[MAXN];
bool viz[MAXN];

int main ()
{

    re = fopen("dijkstra.in", "r");
    we = fopen("dijkstra.out", "w");

    fscanf(re, "%d%d", &n, &m);

    for(int i = 1; i <= m; i++) {
        int a, b, c;
        fscanf(re, "%d%d%d", &a, &b, &c);
        edge nou;
        nou.la = b;
        nou.co = c;
        gf[a].push_back(nou);
    }

    for(int i = 1; i <= n; i++) {
        d[i] = MARE;
    }
    d[1] = 0;

    edge start;
    start.la = 1;
    start.co = 0;
    hdj.push(start);

    while(!hdj.empty()) {
        edge nod = hdj.top();
        hdj.pop();
        if(!viz[nod.la]) {
            viz[nod.la] = true;
            for(auto &it : gf[nod.la]) {
                if(d[nod.la] + it.co < d[it.la]) {
                    d[it.la] = d[nod.la] + it.co;
                    edge topu;
                    topu.la = it.la;
                    topu.co = d[it.la];
                    hdj.push(topu);
                }
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        if(d[i] == MARE) {
            fprintf(we, "0 ");
        } else {
            fprintf(we, "%d ", d[i]);
        }
    }

    fclose(re);
    fclose(we);

    return 0;
}