NOIP2017 逛公园 算是NOIP前补题计划吧

### 输入输出样例

2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0

3
-1

### 说明

【样例解释1】

【测试数据与约定】

$1$ $5$ $5$ $10$ $0$
$2$ $5$ $1000$ $2000$ $0$
$3$ $5$ $1000$ $2000$ $50$
$4$ $5$ $1000$ $2000$ $50$
$5$ $5$ $1000$ $2000$ $50$
$6$ $5$ $1000$ $2000$ $50$
$7$ $5$ $100000$ $200000$ $0$
$8$ $3$ $100000$ $200000$ $50$
$9$ $3$ $100000$ $200000$ $50$
$10$ $3$ $100000$ $200000$ $50$