2019 XCPC Newbie Selection #2 (Nordic Collegiate Programming Contest 2018)

D. Delivery Delays
PDF 题面可用
你可以在这里下载。

单点时限: 5.0 sec

内存限制: 512 MB

样例

Input
4 4
1 2 2
2 3 4
3 4 1
4 1 2
3
1 4 2
3 3 3
4 3 6
Output
6
Input
3 2
1 2 1
3 2 2
4
0 3 1
1 3 3
2 2 4
4 3 6
Output
8