题目描述 小Z在处理一个特殊的最短路径问题，在无向图中有部分边在最初始时是上锁没法通过的，当他拿到位于节点 $k$ 的钥匙后，这些边就可以通过了。 通过一条边的花费为边权值，他想知道从节点 $1$ 走到节点 $n$ 的最小花费是多少。 输入格式 多组样例输入，第一行输入一个整数 $T$ 表示样例数。 对于每个样例，第一行包含三个整数 $n, m, k$，图一共 $n$ 个节点 $m$ 条边，节点编号从 $1$ 到 $n$，钥匙在节点 $k$。 接下来 $m$ 行每行包含四个整数 $s, t, w, v$，表示有一条从 $s$ 到 $t$ 的边，权重为 $w$，如果 $v$ 为 $0$ 则表示不需要钥匙就可以通行，如果是 $1$ 则表示该边需要拿到钥匙后才能通行。 输出格式 对于每组样例，输出一个整数表示从 $1$ 到 $n$ 的最短路，如果不能到达，则输出 $-1$。 输入样例 2 3 3 1 1 2 1 0 2 3 1 0 1 3 5 0 4 4 3 1 3 1 0 1 2 1 0 2 4 1 1 3 4 100 0 输出样例 2 4