#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define NMAX 50005
#define INF 0x3f3f3f3f

using namespace std;

int N, M, cost[NMAX];
bool in_coada[NMAX];
vector <pair <int, int> > graf[NMAX];
queue <int> coada;

void citire()
{
    int a, b, c;

    scanf("%d %d", &N, &M);

    for (int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        graf[a].push_back(make_pair(b, c));
    }

    memset(cost, INF, sizeof(cost));

    cost[1] = 0;
}

void bellman_ford()
{
    int nod;
    vector <pair <int, int> > :: iterator it;

    coada.push(1);
    in_coada[1] = true;

    while (coada.empty() == false)
    {
        nod = coada.front();
        coada.pop();

        for (it = graf[nod].begin(); it != graf[nod].end(); ++it)
            if (cost[it -> first] > cost[nod] + it -> second)
            {
                cost[it -> first] = cost[nod] + it -> second;
                if (in_coada[it -> first] == false)
                {
                    coada.push(it -> first);
                    in_coada[it -> first] = true;
                }
            }
    }
}

void afisare()
{
    for (int i = 2; i <= N; ++i)
        if (cost[i] != INF)
            printf("%d ", cost[i]);
        else
            printf("0 ");
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    citire();
    bellman_ford();
    afisare();

    return 0;
}