#include <cstdio>
#define DIM 250005

const int INF = 1<<30;
struct muchie
{
    int u, v, c, nr;
    muchie()
    {
        nr = 0;
    }
} muchii[DIM];

int d[DIM/5], n, m;

void bell_ford()
{
    bool ok = false;
    while (!ok)
    {
        ok = true;
        for (int i = 1; i <= m; ++i)
            if (d[muchii[i].v] > d[muchii[i].u] + muchii[i].c)
                d[muchii[i].v] = d[muchii[i].u] + muchii[i].c, ok = false;


    }
}

int main()
{
    FILE *file = fopen("dijkstra.in", "r");
    fscanf(file, "%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        d[i] = INF;

    for (int i = 1; i <= m; ++i)
    {
        fscanf(file, "%d%d%d", &muchii[i].u, &muchii[i].v, &muchii[i].c);
        if (muchii[i].u == 1)
            d[muchii[i].v] = muchii[i].c;
    }
    fclose(file);

    bell_ford();
    file = fopen("dijkstra.out", "w");
    for (int i = 2; i <= n; ++i)
        fprintf (file, "%d ", d[i] == INF ? 0 : d[i]);

    fclose(file);

    return 0;
}