#include <bits/stdc++.h>
#include <unordered_set>

using namespace std;
 
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, x, m, a, b;
vector<vector<pair<int, int>>> edges;
vector<int> cost;

class Heap
{
private:
    vector<int> heap;

    void up(int startIndex)
    {
        for (int index = startIndex, parentIndex = index >>= 1; parentIndex > 0; index >>= 1, parentIndex >>= 1)
            if (cost[heap[index]] < cost[heap[parentIndex]])
                swap(heap[index], heap[parentIndex]);
            else
                return;
    }

    void down(int startIndex)
    {
        for (int index = startIndex, childIndex = index << 1;
            childIndex < heap.size();
            index = childIndex, childIndex <<= 1)
        {
            if (childIndex + 1 < heap.size() && cost[heap[childIndex]] > cost[heap[childIndex + 1]])
                ++childIndex;

            if (cost[heap[index]] > cost[heap[childIndex]])
                swap(heap[index], heap[childIndex]);
            else
                return;
        }
    }

public:
    Heap()
    {
        heap.push_back(0); // index from 1
    }

    void push(int x)
    {
        heap.push_back(x);
        up(heap.size() - 1);
    }

    int pop()
    {
        int min = heap[1];

        swap(heap[1], heap[heap.size() - 1]);
        heap.pop_back();
        down(1);

        return min;
    }


    bool empty()
    {
        return heap.size() == 1;
    }
};

int main()
{
    f >> n >> m;
    edges.resize(n + 1);
    cost.resize(n + 1, INT_MAX);

    while (m--)
        f >> x >> a >> b,
        edges[x].push_back({ a, b });

    Heap heap;

    heap.push(1);
    cost[1] = 0;
    while (!heap.empty())
    {
        int x = heap.pop();
        for (auto& next : edges[x])
            if (cost[next.first] > cost[x] + next.second)
            {
                if(cost[next.first] == INT_MAX)
                    heap.push(next.first);

                cost[next.first] = cost[x] + next.second;
            }
    }

    for (int i = 2; i < cost.size(); ++i)
        g << (cost[i] < INT_MAX ? cost[i] : 0) << ' ';

    return 0;
}