Description

学渣小Y走在回家的路上，但是由于前两天大雨地面上水坑无数，为了不让自己心爱的小白鞋弄脏，他必须绕过仍有积水的街道。

但是城市的街道交错复杂，回家晚的话又会被妈妈骂，请你帮助下可怜的小Y吧，帮他找到回家最短的路。

Format

Input

第一行输入两个整数n(n<1000),m(m<1000),n代表有1...n个街道口。m代表有多少城市的通道(小Y的学校在1街道口，家在n街道口。)

第2行到第m+1行输入x,y,z。分别代表x街道口到y街道口有通道，并且长度为z。

第m+2行输入一个整数p(p<1000)，代表有p个通道上有积水。

以下p行输入x,y。代表从x街道口到y街道口有积水不能通行。

Output

输出小Y回家最短的距离。

Samples

4 5
1 4 50
1 2 100
2 4 200
2 3 250
3 4 100
1
1 4

300

Hint

可能会出现重复的路径哦！