MEETINGPOINT - ĐT

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 1e5;
long long d1[N + 1], d2[N + 1], l[N + 1], r[N + 1];
int n, m, k, id[N + 1];
struct TEdge
{
    int u, v, w;
};
TEdge e[2*N + 1];
vector<int> Adj[N + 1];
void read()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
        Adj[e[i].u].push_back(i);
        Adj[e[i].v].push_back(i);
    }
}
struct TPQItem
{
    int u;
    long long dlab;
    bool operator < (const TPQItem & other) const
    {
        return other.dlab < dlab;
    }
    bool Valid(long long d[])
    {
        return d[u] == dlab;
    }
};
priority_queue<TPQItem> PQ;
bool Relax(long long d[], int u, int v, int w)
{
    if (d[v] > d[u] + w)
    {
        d[v] = d[u] + w;
        return true;
    }
    return false;
}
void Dijkstra(int s, long long d[])
{
    fill(d + 1, d + n + 1, 1e18);
    d[s] = 0;
    PQ.push({s, 0});
    while (!PQ.empty())
    {
        TPQItem r = PQ.top();
        PQ.pop();
        if (!r.Valid(d))
        {
            continue;
        }
        int u = r.u;
        for (int i : Adj[u])
        {
            int v = e[i].u ^ e[i].v ^ u;
            if (Relax(d, u, v, e[i].w))
            {
                PQ.push({v, d[v]});
            }
        }
    }
}
bool LF(int x, int y)
{
    return d1[x] * d2[y] < d1[y] * d2[x];
}
void solve()
{
   Dijkstra(1, d1);
   Dijkstra(n, d2);
   iota(id + 1, id + n + 1, 1);
   sort(id + 2, id + n, LF);
   l[0] = 1e18; r[n + 1] = 1e18;
   for (int i = 1; i <= n; ++ i)
   {
       l[i] = min(l[i - 1], d2[id[i]]);
   }
   for (int i = n; i >= 1; -- i)
   {
       r[i] = min(r[i + 1], d1[id[i]]);
   }
   while (k --)
   {
       long long a, b;
       cin >> a >> b;
       int low = 1, high = n;
       while (low <= high)
       {
           int mid = (low + high)/2;
           int j = id[mid];
           if (d1[j] * a < d2[j] * b)
           {
               low = mid + 1;
           }
           else
           {
               high = mid - 1;
           }
       }
       cout << min(r[low] * a, l[high] * b) << '\n';
   }
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen(TASK".INP", "r", stdin);
   //freopen(TASK".OUT", "w", stdout);
   int t = 1;
   bool typetest = false;
   if (typetest)
   {
      cin >> t;
   }
   for (int __ = 1; __ <= t; ++ __)
   {
      read();
      solve();
   }
}