# #27 「 最短路 」

4 4 2
1 2 5 8
1 2 2
2 3 3
1 4 1
4 3 1
1 3
2 4

10
-1

### 数据规模与约定

$n \le 400, m\le n^2, q \le 60000, 0\le v_i, m_i \le 10^5$。

Author: zrt