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

#define NMAX 50005
#define INF 0x3f3f3f3f

using namespace std;

int N, M, cost[NMAX], viz[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));
    }

    for (int i = 2; i <= N; ++i)
        cost[i] = INF;
    ///memset(cost, INF, sizeof(cost))
    coada.push(1);
    viz[1] = 1;
}

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

    while (coada.empty() == false)
    {
        nod = coada.front();
        coada.pop();
        viz[nod] = 0;
        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 (viz[it -> first] == 0)
                {
                    coada.push(it -> first);
                    viz[it -> first] = 1;
                }
            }
        }
    }
}

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();
    bellmanford();
    afisare();

    return 0;
}