#include <fstream>
#include <vector>
#define inf 1000000005
#define N 50005

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, heapSize, lenght[N], prec[N];
vector < pair< int, int > > graph[N];

struct minHeap{
    int node, dist;
};
minHeap heap[N];
int inHeap[N];

pair <int, int> extractMin()
{
    pair <int, int> returnPair;
    returnPair.first = heap[0].node;
    returnPair.second = heap[0].dist;
    inHeap[returnPair.first] = -1;

    inHeap[heap[heapSize - 1].node] = 0;
    swap(heap[0],heap[heapSize - 1]);
    heapSize--;

    int index = 0;

    while(index * 2 + 1 <= heapSize - 1)
    {
        int smallerChildIndex = index * 2 + 1;
        int smallerChildContent = heap[smallerChildIndex].dist;

        if(smallerChildIndex + 1 <= heapSize - 1)
        {
            if(smallerChildContent > heap[smallerChildIndex + 1].dist)
            {
                smallerChildIndex++;
                smallerChildContent = heap[smallerChildIndex].dist;
            }
        }

        if(heap[index].dist > smallerChildContent)
        {
            swap(inHeap[heap[index].node], inHeap[heap[smallerChildIndex].node]);
            swap(heap[index], heap[smallerChildIndex]);
            index = smallerChildIndex;
        }
        else break;
    }

    return returnPair;
}

void update(int index, int value)
{
    heap[index].dist = value;

    while((index - 1) / 2 >= 0 && heap[(index - 1) / 2].dist > heap[index].dist)
    {
        swap(inHeap[heap[index].node], inHeap[heap[(index - 1) / 2].node]);
        swap(heap[index], heap[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

int main()
{
    int x, y, c;
    pair <int, int> P;

    fin >> n >> m;

    while(fin >> x >> y >> c)
    {
        graph[x].push_back(make_pair(y,c));
    }

    heapSize = n;
    for(int i = 1; i <= n; i++)
    {
        heap[i - 1].node = i;
        heap[i - 1].dist = inf;
        inHeap[i] = i - 1;
    }
    heap[0].dist = 0;

    while(heapSize)
    {
        P = extractMin();
        int currentNode = P.first;
        int currentLenght = P.second;
        lenght[currentNode] = currentLenght;
        if(currentNode == 1)
            prec[1] = -1;

        for(auto child : graph[currentNode])
            {
                int childNode = child.first;
                int edgeCost = child.second;
                if(heap[inHeap[childNode]].dist > lenght[currentNode] + edgeCost)
                {
                    prec[childNode] = currentNode;
                    update(inHeap[childNode], lenght[currentNode] + edgeCost);
                }
            }
    }

    for(int i = 2; i <= n; i++)
        fout << lenght[i] << ' ';

    return 0;
}