BOJ_1753

#define INF 987654321
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;

int main(int argc, char * argv[]) 
{
    int n, m, x; scanf("%d%d", &n, &m);
     
    vector<vector<pair<int, int> > > v(n + 1); //<cost, index>
    vector<int> dist(n + 1);
    priority_queue<pair<int, int> > pq;

    int src; scanf("%d", &src);
    for (int i = 0; i < m; ++i) {
        int start, end, cost;
        scanf("%d%d%d", &start, &end, &cost);
        v[start].push_back(make_pair(cost, end));
    }

    for (int i = 0; i < n + 1; ++i)
        dist[i] = INF;
    dist[src] = 0;

    pq.push({0, src});

    while (!pq.empty()) {
        pair<int, int> now = pq.top();
        int now_dist = - now.first;
        int now_index = now.second;

        pq.pop();

        for (int j = 0; j < v[now_index].size(); ++j) {
            int next = v[now_index][j].second;
            if (dist[next] > now_dist + v[now_index][j].first) {
                dist[next] = now_dist + v[now_index][j].first;
                pq.push(make_pair(-dist[next], next));
            }
        }

    }

    for (int k = 1; k <= n; k++) {
        if (dist[k] == INF) 
            printf("INF\n");
        else 
            printf("%d\n", dist[k]);
    }
    
    return 0;
}