MEETING POINT

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;
constexpr ll Inf = 1e17;
int n, m, k, x[N];
vector<pair<int, ll>> adj[N];
ll d[2][N], f[N], g[N];

void Read()
{
    //cin >> n >> m >> k;
  read(n);
  read(m);
  read(k);
  for (int i = 1; i <= m; ++i)
    {
        int u, v;
        ll w;
        //cin >> u >> v >> w;
        read(u), read(v), read(w);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
}

void Dijkstra(int x, ll d[N])
{
    fill_n(d, N, Inf);
    d[x] = 0;
    struct Tque
    {
        int v;
        ll w;
        Tque(int v = 0, ll w = 0) : v(v), w(w) {}
        bool operator<(const Tque &a) const
        {
            return w > a.w;
        }
    };
    priority_queue<Tque> s;
    s.emplace(x, 0);

    while (!s.empty())
    {
        Tque c = s.top();
        s.pop();
        if (d[c.v] != c.w)
            continue;

        for (auto i : adj[c.v])
            if (d[i.first] > c.w + i.second)
            {
                d[i.first] = c.w + i.second;
                s.emplace(i.first, d[i.first]);
            }
    }
}

void Solve()
{
    Dijkstra(1, d[0]);
    Dijkstra(n, d[1]);

    for (int i = 1; i <= n; ++i)
        x[i] = i;

    sort(x + 1, x + n + 1, [&](const int &x, const int &y)
         { return d[0][x] < d[0][y]; });

    f[0] = Inf;
    for (int i = 1; i <= n; ++i)
        f[i] = min(f[i - 1], d[1][x[i]]),
        g[i] = d[0][x[i]];

    while (k--)
    {
        int a, b;
        //cin >> a >> b;
        read(a), read(b);
        int l = 1, mid, h = n;

        while (l <= h)
        {
            mid = (l + h) / 2;
            if (mid == n || f[mid] * b < g[mid + 1] * a)
                h = mid - 1;
            else
                l = mid + 1;
        }

        cout << max(g[l] * a, f[l] * b) << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << "\n";
        Read();
        Solve();
    }
}