# #HDR002C. 不想爬坡

ID: 194 Type: Default 1500ms 128MiB Tried: 74 Accepted: 22 Difficulty: 5 Uploaded By: Tags>图论最短路算法基础二分

# 不想爬坡

## 样例

7 8
0 -50 99 0 99 99 0
1 2 1
2 4 2
1 3 2
3 4 2
4 5 2
4 6 1
5 7 2
6 7 2

6
149

7 8
0 -50 99 0 99 99 0
1 2 2
2 4 2
1 3 2
3 4 2
4 5 2
4 6 2
5 7 2
6 7 2

8
99


## 数据规模与约定

${\tt Subtask 1(10 pts)}$：保证图中仅一条最短路。
${\tt Subtask 2(40 pts)}$$1\leq n \leq 1\times 10^3$
${\tt Subtask 3(50 pts)}$：无特殊限制。

# Related

In following contests:

Hydro Deuterium Round #002