#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();
        viz[nod.la] = true;
        for(auto &it : gf[nod.la]) {
            if(!viz[it.la] && nod.co + it.co < d[it.la]) {
                d[it.la] = nod.co + 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, "-1");
        } else {
            fprintf(we, "%d ", d[i]);
        }
    }

    fclose(re);
    fclose(we);

    return 0;
}