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

using namespace std;

int cost[50000];
short visited[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;
        int temp;
        while (cost[heap[parent]] > cost[heap[i]])
        {
            temp = heap[parent];
            heap[parent] = heap[i];
            heap[i] = temp;
            i = parent;
            parent = i << 1;
        }
    }
    static void insert(int i)
    {
        heap[++heapSize] = i;
        upheap(i);
    }
    static int readAndRemove(int i)
    {
        int ret = heap[i];
        heap[i] = heap[heapSize--];
        if (heapSize)
            downheap(i);
        return ret;
    }
    static void downheap(int i)
    {
        int child = i >> 1;
        int temp;
        while (heapSize <= child)
        {
            if (heapSize <= child+1)
            {
                if (cost[heap[child]] > cost[heap[child+1]])
                {
                    if (cost[heap[i]] > cost[heap[++child]])
                    {
                        temp = heap[child];
                        heap[child] = heap[i];
                        heap[i] = temp;
                        i = child;
                        child = i >> 1;
                    }
                }
                else if (cost[heap[i]] > cost[heap[child]])
                {
                    temp = heap[child];
                    heap[child] = heap[i];
                    heap[i] = temp;
                    i = child;
                    child = i >> 1;
                }
            }
            else if (cost[heap[i]] > cost[heap[child]])
            {
                temp = heap[child];
                heap[child] = heap[i];
                heap[i] = temp;
                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;
    }
    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 (!visited[_muchie.x])
            {
                visited[_muchie.x] = 1;
                HeapClass::insert(_muchie.x);
            }
        }

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

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