游戏
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定 n 个点， m 条边的无向图
每条边有一个花费和状态，状态为 0 表示该边处于锁定状态暂时不可通过， 1 表示可以通过
在节点 k 有一把钥匙，你取得钥匙后，便可以正常通过 0 状态边
现在你从 1 节点出发，需要求出到达节点 n 的最小花费

输入描述:

第一行三个整数 n, m, k ，分别表示节点数，边数，钥匙所在节点
接下来 m 行，每行四个整数 a_i, b_i, c_i, d_i ，表示 a_i 到 b_i 之间存在一条无向边，通过该边花费 c_i ，其状态为 d_i ， d_i 取值仅为 0 或 1

输出描述:

输出节点 1 到 n 的最小花费，如果无法到达，输出 -1
示例1

输入

复制 
6 10 5
1 2 1 1
2 4 9 1
4 5 4 1
1 3 9 1
3 6 8 0
4 6 6 0
4 5 1 0
5 6 10 0
5 6 5 0
5 6 6 1

输出

复制 
19
示例2

输入

复制 
6 10 5
1 6 4 1
6 3 9 1
3 5 8 1
1 2 10 0
3 4 2 1
4 5 2 0
3 4 5 1
3 6 6 1
5 6 1 0
3 5 10 1

输出

复制 
4

备注:

1 \le n \le 2 \times 10^5, 0 \le m \le 10^5, 1 \le k, ai, bi \le n, 1 \le ci \le 2 \times 10^5