#include <stdio.h>
#include <stdlib.h>

#define MAX_N    50005
#define MAX_M    250005
#define MAX_HEAP 500005

typedef struct
{
    void* next;
    int node;
    int distance;
} List;

typedef struct 
{
    int node;
    int distance;
} HeapType;

List* graph[MAX_N];
List* finalNodes[MAX_N];
int   distances[MAX_N];
int   isInQueue[MAX_N];

HeapType heap[MAX_HEAP];
int heapLength = 0;

void AddToGraph(int node1, int nodeToAdd, int distance)
{
    List* newNode = (List*)malloc(sizeof(List));

    newNode->next = NULL;
    newNode->node = nodeToAdd;
    newNode->distance = distance;

    if(finalNodes[node1] == NULL)
    {
        finalNodes[node1] = newNode;
        graph[node1] = newNode;
    }
    else
    {
        finalNodes[node1]->next = newNode;
        finalNodes[node1] = newNode;
    }
}

void Percolate(int position)
{
    if(position >= 1)
    {
        int prevIndex = position / 2;
        if(prevIndex >= 1)
        {
            HeapType prevVal = heap[prevIndex];
            if(prevVal.distance > heap[position].distance)
            {
                HeapType tmp = heap[position];
                heap[position] = heap[prevIndex];
                heap[prevIndex] = tmp;

                Percolate(prevIndex);
            }
        }
    }
}

void SiftDown(int position)
{
    if(position <= heapLength)
    {
        int next1 = position * 2;
        int next2 = next1 + 1;

        if(next1 <= heapLength)
        {
            int bestIndex = next1;

            if(next2 <= heapLength)
            {
                if(heap[next2].distance < heap[next1].distance)
                {
                    bestIndex = next2;
                }
            }

            if(heap[bestIndex].distance < heap[position].distance)
            {
                HeapType tmp = heap[bestIndex];
                heap[bestIndex] = heap[position];
                heap[position] = tmp;

                SiftDown(bestIndex);
            }
        }
    }
}

void InsertHeap(HeapType data)
{
    heap[++heapLength] = data;
    Percolate(heapLength);
}

int DeleteBestHeap(HeapType* crtNode)
{
    if(heapLength)
    {
        HeapType lastNode = heap[1];
        *crtNode = lastNode;

        heapLength--;
        if(heapLength)
        {
            heap[1] = heap[heapLength + 1];
            SiftDown(1);
        }
        return 1;
    }

    return 0;
}

void BFS()
{
    HeapType crtNode;
    crtNode.node = 1;
    crtNode.distance = 0;

    distances[1] = 0;
    isInQueue[1] = 1;

    InsertHeap(crtNode);

    while(DeleteBestHeap(&crtNode))
    {
        int crtDist = distances[crtNode.node];
        isInQueue[crtNode.node] = 0;

        List* elem = graph[crtNode.node];
        while(elem)
        {
            int newDist = crtDist + elem->distance;
            if(distances[elem->node] == -1 || newDist < distances[elem->node])
            {
                distances[elem->node] = newDist;
                HeapType elementToHeap;
                
                if(!isInQueue[elem->node])
                {
                    elementToHeap.distance = newDist;
                    elementToHeap.node = elem->node;

                    InsertHeap(elementToHeap);

                    isInQueue[elementToHeap.node] = 1;
                }
            }
            elem = (List*)elem->next;
        }
    }
}

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

    fscanf(fin, "%d %d", &n, &m);

    for(int i = 0; i < m; i++)
    {
        int node1, node2, distance;
        fscanf(fin, "%d %d %d", &node1, &node2, &distance);
        AddToGraph(node1, node2, distance);
    }

    for(int i = 0; i <= n; i++)
    {
        distances[i] = -1;
    }

    BFS();

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

    fclose(fin);
    fin = NULL;
    fclose(fout);
    fout = NULL;

    return 0;
}