#include <fstream>
#include <vector>
using namespace std;

const int maxNodes = 50000;
const int INF = 250000001;

struct Edge
{
    int rightEnd;
    int length;
    Edge(int y, int d)
    {
        rightEnd = y;
        length = d;
    }
};

int leftSon(int i);
int rightSon(int i);
int parent(int i);
void siftUp(int pos, int hPos[], int heap[], int dist[]);
void siftDown(int pos, int hPos[], int heap[], int dist[], int N);
void pop(int hPos[], int heap[], int &N);
int top(int heap[], int N);

int main()
{
    int N, M, i;
    ifstream f("dijkstra.in");
    f >> N >> M;
    int cN = N;
    vector<Edge> adjList[N + 1];
    int x, y, d;
    for (i = 0; i < M; i++)
    {
        f >> x >> y >> d;
        adjList[x].push_back(Edge(y, d));
    }
    f.close();

    int hPos[maxNodes + 1], heap[N], dist[N + 1];
    for (i = 0; i < N; i++)
    {
        heap[i] = i + 1;
        hPos[heap[i]] = i;
        dist[heap[i]] = INF;
    }
    dist[1] = 0;

    for (i = N / 2 - 1; i >= 0; i--)
        siftDown(i, hPos, heap, dist, N);

    while (N >= 0)
    {
        x = top(heap, N);
        pop(hPos, heap, N);
        siftDown(0, hPos, heap, dist, N);
        for (i = 0; i < adjList[x].size(); i++)
        {
            if (dist[x] + adjList[x][i].length < dist[adjList[x][i].rightEnd])
            {
                dist[adjList[x][i].rightEnd] = dist[x] + adjList[x][i].length;
                siftDown(hPos[adjList[x][i].rightEnd], hPos, heap, dist, N);
                siftUp(hPos[adjList[x][i].rightEnd], hPos, heap, dist);
            }
        }
    }

    ofstream g("dijkstra.out");
    for (i = 2; i <= cN; i++)
        if (dist[i] == INF)
            g << 0 << " ";
        else
            g << dist[i] << " ";
    g.close();

    return 0;
}

int leftSon(int i)
{
    return 2 * i + 1;
}

int rightSon(int i)
{
    return 2 * i + 2;
}

int parent(int i)
{
    return (i - 1) / 2;
}

void siftUp(int pos, int hPos[], int heap[], int dist[])
{
    while (pos && dist[heap[parent(pos)]] > dist[heap[pos]])
    {
        swap(hPos[heap[parent(pos)]], hPos[heap[pos]]);
        swap(heap[parent(pos)], heap[pos]);
        pos = parent(pos);
    }
}

void siftDown(int pos, int hPos[], int heap[], int dist[], int N)
{
    bool swapped = true;
    int minPos;
    while (leftSon(pos) < N && swapped)
    {
        minPos = pos;
        swapped = false;
        if (dist[heap[leftSon(pos)]] < dist[heap[pos]])
            minPos = leftSon(pos);
         if (rightSon(pos) < N && dist[heap[rightSon(pos)]] < dist[heap[minPos]])
            minPos = rightSon(pos);

        if (minPos != pos)
        {
            swapped = true;
            swap(hPos[heap[minPos]], hPos[heap[pos]]);
            swap(heap[minPos], heap[pos]);
            pos = minPos;
        }
    }
}

void pop(int hPos[], int heap[], int &N)
{
    if (N > 0)
    {
        hPos[heap[N - 1]] = 0;
        heap[0] = heap[N - 1];
        N--;
    }
    else if (N == 0)
        N--;
}

int top(int heap[], int N)
{
    if (N >= 0)
        return heap[0];
    return -1;
}