2282 - 【NOIP2017】D1T3. 逛公园

Input

Output

输出文件包含 T 行，每行一个整数代表答案。

Examples

Input

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

Output

3
-1

Hint

【样例说明】

对于第一组数据，最短路为 3。 1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 3 条合法路径。

【数据规模与约定】

Time Limit 3 seconds
Memory Limit 512 MB
Discuss Stats
上一题 下一题