#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Teleport
{
 bool hasTeleport;
 int  to;
 int  firstTime;
 int  interval;
 int  getNextOddTime(int t)  // t 시간 이후로 teleport가 되는 홀수 시간 (t 시간을 포함하지 않는다)
 {
  if (interval % 2 == 0 && firstTime % 2 == 0) return -1;
  int ret = -1;
  int x = t / interval;
  if (interval % 2 == 0)
  {
   ret = x * interval + firstTime;
   if (ret <= t) ret += interval;
  }
  else
  {
   if (x % 2 == firstTime % 2) ++x;
   ret = x * interval + firstTime;
   if (ret <= t) ret += interval * 2;
  }
  return ret;
 }
 int  getNextEvenTime(int t)
 {
  if (interval % 2 == 0 && firstTime % 2 == 1) return -1;
  int ret = -1;
  int x = t / interval;
  if (interval % 2 == 0)
  {
   ret = x * interval + firstTime;
   if (ret <= t) ret += interval;
  }
  else
  {
   if (x % 2 != firstTime % 2) ++x;
   ret = x * interval + firstTime;
   if (ret <= t) ret += interval * 2;
  }
  return ret;
 }
 bool isTeleportTime(int t)
 {
  return (t % interval == firstTime);
 }
};
struct Node
{
 int visited[2];
 bool processed[2];
 vector<int> edge;
};
Node node[1000];
Teleport tel[1000];
int n, m, t;
struct travel
{
 int now;
 int time;
 bool operator < (const travel& rhs) const
 {
  return time > rhs.time;
 }
};
void go(int start)
{
 priority_queue<travel> q;
 travel c, d;
 c.now = start;
 if (node[start].visited[0] != 2147483647)
 {
  c.time = node[start].visited[0];
  q.push(c);
 }
 if (node[start].visited[1] != 2147483647)
 {
  c.time = node[start].visited[1];
  q.push(c);
 }
 while (!q.empty())
 {
  c = q.top(); q.pop();
  if (node[c.now].processed[c.time % 2]) continue;
  if (node[c.now].edge.empty()) continue;
  node[c.now].processed[c.time % 2] = true;
  d.time = c.time + 1;
  for (size_t i = 0; i < node[c.now].edge.size(); ++i)
  {
   d.now = node[c.now].edge[i];
   if (tel[d.now].hasTeleport)
   {
    if (tel[d.now].isTeleportTime(d.time))
    {
     if (d.now == n - 1)
     { // 성배방인 경우 시간 - 2를 넣어서 d.time 시간에 성배방에서 바로 순간이동할 수 있게 한다.
      node[d.now].visited[d.time % 2] <?= d.time - 2;
     }
     d.now = tel[d.now].to;
    }
   }
   if (node[d.now].visited[d.time % 2] > d.time)
   {
    node[d.now].visited[d.time % 2] = d.time;
    q.push(d);
   }
  }
  if (tel[c.now].hasTeleport)
  {
   d.now = tel[c.now].to;
   if (c.time % 2 == 0)
    d.time = tel[c.now].getNextEvenTime(c.time);
   else
    d.time = tel[c.now].getNextOddTime(c.time);
   if (d.time != -1 && node[d.now].visited[d.time % 2] > d.time)
   {
    node[d.now].visited[d.time % 2] = d.time;
    q.push(d);
   }
  }
 }
}
int solve()
{
 node[0].visited[0] = 0;
 go(0);
 if (node[n - 1].visited[0] != 2147483647 || node[n - 1].visited[1] != 2147483647)
 {
  for (int i = 0; i < n - 1; ++i)
  {
   node[i].visited[0] = node[i].visited[1] = 2147483647;
   node[i].processed[0] = node[i].processed[1] = false;
  }
  node[n - 1].processed[0] = node[n - 1].processed[1] = false;
  go(n - 1);
  int result = min(node[0].visited[0], node[0].visited[1]);
  if (result == 2147483647) return -1;
  return result;
 }
 return -1;
}
int main()
{
 int T;
 scanf("%d", &T);
 while (T--)
 {
  scanf("%d%d%d", &n, &m, &t);
  for (int i = 0; i < n; ++i)
  {
   tel[i].hasTeleport = false;
   node[i].visited[0] = node[i].visited[1] = 2147483647;
   node[i].processed[0] = node[i].processed[1] = false;
   node[i].edge.clear();
   node[i].edge.reserve(1000);
  }
  for (int i = 0; i < m; ++i)
  {
   int x, y;
   scanf("%d%d", &x, &y);
   node[x].edge.push_back(y);
   node[y].edge.push_back(x);
  }
  for (int i = 0; i < t; ++i)
  {
   int x, y, q, w;
   scanf("%d%d%d%d", &x, &y, &q, &w);
   tel[x].hasTeleport = true;
   tel[x].to = y;
   tel[x].firstTime = q;
   tel[x].interval = w;
  }
  printf("%dn", solve());
 }
}