#include <fstream>
#include <vector>

using namespace std;

class PriorityQueue
{
public:
    PriorityQueue(int n) :
        key_index(vector<int>(n, -1)) { }

    void Add(int key, int value);
    void ChangeValue(int key, int new_value);
    pair<int, int> RemoveFirst();

    int Size() const { return heap.size(); }
    bool Empty() const { return Size() <= 0; }

private:
    vector<pair<int, int>> heap;
    vector<int> key_index;

    int Father(int pos) const { return pos / 2; }
    int LeftSon(int pos) const { return 2 * pos; }
    int RightSon(int pos) const { return 2 * pos + 1; }

    void Swap(int a, int b)
    {
        swap(key_index[heap[a].first], key_index[heap[b].first]);
        swap(heap[a], heap[b]);
    }

    bool Smaller(int a, int b) const { return heap[a].second < heap[b].second; }

    void Percolate(int pos);
    void Sift(int pos);
};

void PriorityQueue::Add(int key, int val)
{
    if (key_index[key] != -1) {
        ChangeValue(key, val);
        return;
    }

    heap.push_back({key, val});
    key_index[key] = Size() - 1;
    Percolate(Size() - 1);
}

void PriorityQueue::ChangeValue(int key, int new_val)
{
    if (key_index[key] == -1)
        return;

    int ind = key_index[key];
    heap[ind].second = new_val;

    if (Father(ind) != ind && Smaller(ind, Father(ind)))
        Percolate(ind);
    else Sift(ind);
}

pair<int, int> PriorityQueue::RemoveFirst()
{
    if (Size() <= 0)
        return {-1, -1};

    auto p = heap[0];
    Swap(0, Size() - 1);
    key_index[heap.back().first] = -1;

    heap.pop_back();
    Sift(0);
    return p;
}

void PriorityQueue::Percolate(int pos)
{
    while (Father(pos) != pos && Smaller(pos, Father(pos))) {
        Swap(pos, Father(pos));
        pos = Father(pos);
    }
}

void PriorityQueue::Sift(int pos)
{
    if (LeftSon(pos) < Size()) {
        int son = LeftSon(pos);
        if (RightSon(pos) < Size() && Smaller(RightSon(pos), son))
            son = RightSon(pos);
        if (Smaller(son, pos)) {
            Swap(son, pos);
            Sift(son);
        }
    }
}

struct Node
{
    int cost;
    vector<pair<int, int>> edges;
};

using Graph = vector<Node>;

const int kInfinite = (1 << 30);

void FindMinCosts(Graph &g, int start)
{
    for (auto &node : g)
        node.cost = kInfinite;
    g[start].cost = 0;

    PriorityQueue q(g.size());
    for (int i = 0; i < g.size(); ++i)
        q.Add(i, g[i].cost);

    while (!q.Empty()) {
        int node = q.RemoveFirst().first;
        for (const auto &edge : g[node].edges) {
            int new_cost = g[node].cost + edge.second;
            if (new_cost < g[edge.first].cost) {
                g[edge.first].cost = new_cost;
                q.ChangeValue(edge.first, new_cost);
            }
        }
    }
}

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

    int n, m;
    fin >> n >> m;

    Graph graph(n);
    while (m--) {
        int x, y, w;
        fin >> x >> y >> w;
        graph[x - 1].edges.push_back({y - 1, w});
    }

    FindMinCosts(graph, 0);
    for (int i = 1; i < n; ++i)
        fout << (graph[i].cost == kInfinite ? 0 : graph[i].cost) << " ";

    return 0;
}