#include <bits/stdc++.h>
using namespace std;

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << '\n'; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

int main() {
    Int n, m, q;
    cin >> n >> m >> q;
    vector<pair<Int, Int>> a(m);
    for (Int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
        a[i].first--, a[i].second--;
    }
    vector<pair<Int, Int>> b(q);
    for (Int i = 0; i < q; i++) {
        cin >> b[i].first >> b[i].second;
        b[i].first--, b[i].second--;
    }
    vector<vector<Int>> v(n);
    for (Int i = 0; i < m; i++) {
        v[a[i].first].push_back(a[i].second);
    }
    for (Int i = 0; i < n; i++) {
        sort(all(v[i]));
        v[i].push_back(INF);
    }
    for (Int i = 0; i < q; i++) {
        Int res = 0;
        for (Int j = 0; j < n; j++) {
            if (j < b[i].first) continue;
            if (b[i].second < j) break;
            res += upper_bound(all(v[j]), b[i].second) - v[j].begin();
        }
        print(res);
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Dijkstra {
    explicit Dijkstra(size_t size) : size(size), G(size) {}

    struct edge {
        edge(int to, T cost) : to(to), cost(cost) {}

        int to;
        T cost;
    };

    using P = pair<T, int>;
    const T inf = numeric_limits<T>::max();

    size_t size;
    vector<vector<edge>> G;
    vector<T> d;

    void add_edge(int u, int v, T c) {
        G[u].push_back(edge(v, c));
    }

    void build(int s) {
        d.assign(size, inf);
        priority_queue<P, vector<P>, greater<>> q;

        d[s] = 0;
        q.push(P(0, s));

        while (!q.empty()) {
            P p = q.top();
            q.pop();
            int v = p.second;
            if (d[v] < p.first) continue;
            for (auto &e : G[v])
                if (d[e.to] > p.first + e.cost) {
                    d[e.to] = p.first + e.cost;
                    q.push(P(d[e.to], e.to));
                }
        }
    }

    T operator[](int v) {
        return d[v];
    }
};

int main() {
    int V, E, r;
    cin >> V >> E >> r;

    auto g = Dijkstra<int>(V);
    for (int i = 0; i < E; ++i) {
        int s, t, c;
        cin >> s >> t >> c;
        g.add_edge(s, t, c);
    }

    g.build(r);
    for (int i = 0; i < V; ++i) {
        if (g[i] != g.inf) {
            cout << g[i] << endl;
        } else {
            cout << "INF" << endl;
        }
    }
    return 0;
}
