MEETING POINT

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#define task "MEETINGPOINT"
using namespace std;
using ll = long long;

const int N = 1e5 + 2;
ll d[3][N];
struct Edge
{
    int v;
    ll w;
    Edge(int u, ll r)
    {
        v = u;
        w = r;
    }
};
vector<Edge> adj[N];
const ll Inf = 1e18 + 7;
int n, m, k, id[N];
ll minn[N], a, b;

void Read()
{
    cin >> n >> m >> k;
    while (m--)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back(Edge(v, w));
        adj[v].push_back(Edge(u, w));
    }
}

void Init(ll d[], int x)
{
    fill_n(d, N, Inf);
    d[x] = 0;
}

bool Relax(ll d[], int par, int son, ll w)
{
    if (d[son] > d[par] + w)
    {
        d[son] = d[par] + w;
        return true;
    }
    return false;
}

void Dijkstra(ll d[], int x)
{
    Init(d, x);
    struct Tque
    {
        int v;
        ll w;
        Tque() {}
        Tque(int m, ll n)
        {
            v = m;
            w = n;
        }
        bool operator<(const Tque &a) const
        {
            return w > a.w;
        }
        bool Valid(ll d[])
        {
            return d[v] == w;
        }
    };
    vector<bool> ck(N);
    priority_queue<Tque> s;
    s.push(Tque(x, 0));
    while (s.size())
    {
        //cin >> a >> b;
        Tque c = s.top();
        s.pop();
        if (!c.Valid(d) || ck[c.v])
            continue;
        ck[c.v] = 1;
        for (Edge i : adj[c.v])
            if (Relax(d, c.v, i.v, i.w))
                s.push(Tque(i.v, d[i.v]));
    }
}

bool Check(ll v)
{
    int l = 1, m, h = n;
    while (l <= h)
    {
        m = (l + h) / 2;
        if (d[1][id[m]] * a <= v)
            l = m + 1;
        else
            h = m - 1;
    }
    return h > 0 && minn[h] * b <= v;
}

void Solve()
{
    Dijkstra(d[1], 1);
    Dijkstra(d[2], n);
    for (int i = 1; i <= n; ++i)
        id[i] = i;
    sort(id + 1, id + n + 1, [&](int &x, int &y) { return d[1][x] < d[1][y]; });
    minn[0] = Inf;
    for (int i = 1; i <= n; ++i)
        minn[i] = min(minn[i - 1], d[2][id[i]]);
    while (k--)
    {
        cin >> a >> b;
        ll l = 0, m, h = Inf;
        while (l <= h)
        {
            //cerr << m << "\n";
            m = (l + h) / 2;
            if (Check(m))
                h = m - 1;
            else
                l = m + 1;
        }
        cout << l << "\n";
    }
}

main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    Read();
    Solve();
}