#include <fstream>
#include <queue>
#include <list>

using namespace std;

int cost[50000];
short pozition[50000];
struct muchie
{
    int x;
    int c;
};
list <muchie> adiacList[50000];
class HeapClass
{
public:
    static int heap[50000];
    static int heapSize;
    static void upheap(int i)
    {
        int parent = i >> 1;
        while (cost[heap[parent]] > cost[heap[i]])
        {
            swap (i, parent);
            i = parent;
            parent = i >> 1;
        }
    }
    static void insert(int i)
    {
        heap[++heapSize] = i;
        pozition[heap[heapSize]] = heapSize;
        upheap(heapSize);
    }
    static void swap(int i, int j)
    {
        pozition[heap[j]] = i;
        pozition[heap[i]] = j;
        int temp = heap[j];
        heap[j] = heap[i];
        heap[i] = temp;
    }
    static int readAndRemove(int i)
    {
        int ret = heap[i];
        heap[i] = heap[heapSize--];
        pozition[heap[i]] = i;
        if (heapSize >= i)
            downheap(i);
        return ret;
    }
    static void downheap(int i)
    {
        int child = i << 1;
        int temp;
        while (heapSize >= child)// swap so it gets mimimal value on cost[heap[i]]
        {
            if (heapSize >= child+1)
            {
                if (cost[heap[child]] > cost[heap[child+1]])
                {
                    if (cost[heap[i]] > cost[heap[++child]])
                    {
                        swap(i, child);
                        i = child;
                        child = i << 1;
                    }
                }
                else if (cost[heap[i]] > cost[heap[child]])
                {
                    swap(i, child);
                    i = child;
                    child = i << 1;
                }
                else return;
            }
            else if (cost[heap[i]] > cost[heap[child]])
            {
                swap(i, child);
                i = child;
                child = i << 1;
            }
            else return;
        }
    }
};
int HeapClass::heapSize;
int HeapClass::heap[50000];

int main()
{
    FILE * fin = fopen("dijkstra.in", "r");
    FILE * fout = fopen("dijkstra.out", "w");

    int n, m, i, j;
    muchie _muchie;
    fscanf(fin, "%d%d", &n, &m);
    for (i = 0; i < m; ++i)
    {
        fscanf(fin, "%d%d%d", &j, &_muchie.x, &_muchie.c);
        adiacList[j].push_back(_muchie);
    }
    for (i = 2; i <= n; ++i)
    {
        cost[i] = 0x7fffffff;
        pozition[i] = -1;
    }
    HeapClass::insert(1);
    while (HeapClass::heapSize)
    {
        i = HeapClass::readAndRemove(1);
        while(adiacList[i].size())
        {
            _muchie = adiacList[i].front();
            adiacList[i].pop_front();
            if(cost[i] + _muchie.c < cost[_muchie.x])
            {
                cost[_muchie.x] = cost[i] + _muchie.c;
                if (pozition[_muchie.x] == -1)
                {
                    HeapClass::insert(_muchie.x);
                } else {
                    HeapClass::upheap(pozition[_muchie.x]);
                }
            }
        }

    }
    for (i = 2; i <= n; ++i)
    {
        fprintf(fout, "%d ", (cost[i] == 0x7fffffff) ? 0 : cost[i]);
    }
    fprintf(fout, "\n");

    fclose(fin);
    fclose(fout);
    return 0;
}