#include <fstream>
#include <vector>
#define NMAX 50001
#define inf 2000000000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector< pair < int, int>> v[NMAX]; // v[x].first - numarul nodului vecin cu x, v[x].second - costul drumului din x in y

int heap[NMAX], pos[NMAX], d[NMAX], n, m, l = 0;

int left_son(int k)
{
    return 2*k;
}

int right_son(int k)
{
    return 2*k + 1;
}

int father(int k)
{
    return k/2;
}

void change(int a, int b)
{
    int aux;

    aux = heap[a];
    heap[a] = heap[b];
    heap[b] = aux;

    aux = pos[heap[a]];
    pos[heap[a]] = pos[heap[b]];
    pos[heap[b]] = aux;
}

void go_down(int k)
{
    int aux;

    do
    {
        aux = 0;

        if (left_son(k) <= l)
        {
            aux = left_son(k);

            if (right_son(k) <= l && d[heap[right_son(k)]] < d[heap[k]])
                aux = right_son(k);

            if (d[heap[k]] <= d[heap[left_son(k)]] && d[heap[k]] <= d[heap[right_son(k)]])
                aux = 0;

            if (aux)
            {
                change(aux, k);
                k = aux;
            }
        }
    } while (aux);
}

void go_up(int k)
{
    while(k > 1 && d[heap[k]] < d[heap[father(k)]])
    {
        change(k, father(k));
        k = father(k);
    }
}

void dijkstra()
{
    for (int i=2; i<=n; ++i)
    {
        d[i] = inf;
        pos[i] = -1;
    }

    l++;
    pos[1] = 1;
    heap[l] = 1;

    while (l)
    {
        int minim = heap[1];
        change(1, l);
        pos[heap[1]] = 1;
        l --;

        go_down(1);

        for (int i=0; i<v[minim].size(); ++i)
        {
            if (d[v[minim][i].first] > d[minim] + v[minim][i].second)
            {
                d[v[minim][i].first] = d[minim] + v[minim][i].second;

                if (pos[v[minim][i].first] != -1)
                    go_up(pos[v[minim][i].first]);
                else
                {
                    heap[++l] = v[minim][i].first;
                    pos[heap[l]] = l;
                    go_up(l);
                }
            }
        }

    }
}

int main()
{
    f >> n >> m;

    for (int i=1; i<=m; ++i)
    {
        int a, b, c;
        f >> a >> b >> c;
        v[a].push_back(make_pair(b,c));
    }

    dijkstra();

    for (int i=2; i<=n; ++i)
        if (d[i] == inf)
            g << "0 ";
        else
            g << d[i] << " ";
    return 0;
}