# #NOIPS2017C. 逛公园

ID: 73 Type: Default 3000ms 512MiB Tried: 9 Accepted: 4 Difficulty: 9 Uploaded By: Tags>NOIP 提高组2017

# 逛公园

## 输出格式

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, 1 - 2 - 4 - 5, 1 - 2 - 3 - 5$$3$ 条合法路径。

## 数据范围与提示

$1$ $5$ $5$ $10$ $0$
$2$ $10^3$ $2\times 10^3$
$3$ $50$
$4$
$5$
$6$
$7$ $10^5$ $2\times 10^5$ $0$
$8$ $3$ $50$
$9$
$10$