#include <fstream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

const int INF = 1e9;

struct Node
{
    int v, d;
    Node* next;
    Node(int v, int d, Node* next = nullptr) : v(v), d(d), next(next) {}
};

auto cmp = [](auto& a, auto& b) {
    return a.first > b.first; // Min-heap based on distance
    };


void upheap(int id, std::vector<pair<int, int>>& heap, std::vector<int>& inheap)
{
    while (id > 1)
    {
        int parent = id / 2;
        if (cmp(heap[parent], heap[id]))
        {
            std::swap(heap[id], heap[parent]);
            inheap[heap[id].second] = id;
            inheap[heap[parent].second] = parent;
            id = parent;
        }
        else
        {
            return;
        }
    }
}

void downheap(int id, std::vector<pair<int, int>>& heap, std::vector<int>& inheap)
{
    int n = heap.size() - 1;
    while (id * 2 <= n)
    {
        int left_child = id * 2;
        int right_child = id * 2 + 1;
        int smallest = id;
        if (left_child <= n && cmp(heap[smallest], heap[left_child]))
        {
            smallest = left_child;
        }
        if (right_child <= n && cmp(heap[smallest], heap[right_child]))
        {
            smallest = right_child;
        }
        if (smallest != id)
        {
            std::swap(heap[id], heap[smallest]);
            inheap[heap[id].second] = id;
            inheap[heap[smallest].second] = smallest;
            id = smallest;
        }
        else
        {
            return;
        }
    }
}

pair<int, int> removeMin(vector<pair<int, int>>& heap, vector<int>& inheap)
{
    std::pair<int, int> minElement = heap[1];
    inheap[minElement.second] = -1; // Mark as removed
    heap[1] = heap.back();
    heap.pop_back();
    if (!heap.empty())
    {
        inheap[heap[1].second] = 1;
        downheap(1, heap, inheap);
    }
    return minElement;
}

std::vector<int> dijkstra(int start, int n, vector<Node*>& graph)
{
    std::vector<pair<int, int>> heap(n + 1, { INF, -1 });
    vector<int> inheap(n + 1, -1);
    for (int i = 1; i <= n; ++i)
    {
        heap[i].first = INF;
        heap[i].second = i;
    }

    std::make_heap(heap.begin() + 1, heap.end(), cmp);

    for (int i = 1; i <= n; ++i)
    {
        inheap[heap[i].second] = i;
    }

    int id = inheap[start];
    heap[id].first = 0;

    upheap(id, heap, inheap);

    vector<int> dist;
    dist.resize(n + 1, INF);
    dist[start] = 0;

    for (int i = 1; i < n; ++i)
    {
        if (heap.size() <= 1)
            break;

        auto minElement = removeMin(heap, inheap);
        int u = minElement.second;
        int d = minElement.first;

        if (d == INF)
            break;

        Node* current = graph[u];
        while (current != nullptr)
        {
            int v = current->v;
            int w = current->d;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                heap[inheap[v]].first = dist[v];
                upheap(inheap[v], heap, inheap);
            }
            current = current->next;
        }
    }
    return dist;
}

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

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

    vector<Node*> graph(n + 1, nullptr);

    for (int i = 0; i < m; ++i)
    {
        int u, v, d;
        fin >> u >> v >> d;
        graph[u] = new Node(v, d, graph[u]);
    }

    vector<int> dist = dijkstra(1, n, graph);

    for (int i = 2; i <= n; ++i)
    {
        if (dist[i] == INF)
            fout << "INF\n";
        else
            fout << dist[i] << " ";
    }
    return 0;
}