#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define NMAX 50005
#define inf 2000000000

using namespace std;

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

int i, n, m, x, y, dist, d[NMAX], nn = 0;
bool visited[NMAX];

struct hp
{
    int x, y;
};

vector < hp > v[NMAX];
hp heap[2*NMAX];

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

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

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

void get_down(int k)
{
    int aux;

    do
    {
        aux = 0;

        if (left_son(k) <= nn)
            aux = left_son(k);

        if (right_son(k) <= nn && heap[right_son(k)].y < heap[aux].y)
            aux = right_son(k);

        if (left_son(k) <= nn && right_son(k) <= nn)
            if (heap[left_son(k)].y > heap[k].y && heap[right_son(k)].y > heap[k].y)
                aux = 0;

        if (aux)
        {
            swap(heap[k], heap[aux]);
            k = aux;
        }
    }while (aux);
}

void get_up(int k)
{
    while (k > 1 && heap[k].y < heap[father(k)].y)
    {
        swap(heap[k], heap[father(k)]);
        k = father(k);
    }
}

void insert_heap(hp x)
{
    heap[++nn] = x;
    get_up(nn);
}

void delete_heap(int k)
{
    heap[k] = heap[nn];
    heap[nn].y = inf;
    nn --;
    get_down(k);
}

void dijkstra()
{
    hp h;
    h.x = 1;
    h.y = 0;
    insert_heap(h);

    while (nn)
    {
        int minim = heap[1].x;
        delete_heap(1);

        for (vector < hp > :: iterator it = v[minim].begin(); it != v[minim].end(); ++it)
            if (d[it -> x] > d[minim] + it -> y)
        {
            d[it -> x] = d[minim] + it -> y;
            insert_heap(*it);
        }
    }
}

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

    for (i = 1; i <= m; ++ i)
    {
        f >> x >> y >> dist;
        hp c;
        c.x = y;
        c.y = dist;
        v[x].push_back(c);
    }

    for (i = 2; i <= n; ++ i)
        d[i] = inf;

    dijkstra();

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