ประเทศ IOI ประกอบด้วยเมือง $N$ เมืองตั้งแต่เมือง $1$ ถึงเมือง $N$ โดยแต่ละเมืองเชื่อมต่อกันด้วยถนน ในประเทศ IOI มีถนน $K$ สาย และถนนทุกสายเชื่อมต่อระหว่างเมืองที่แตกต่างกัน $2$ เมือง รถยนต์สามารถวิ่งไปกลับได้ทั้งสองทิศทางอย่างอิสระบนถนน แต่ไม่สามารถเดินทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งโดยไม่ผ่านถนนได้

JOI-kun ซึ่งอาศัยอยู่ที่เมือง $1$ ของประเทศ IOI ตัดสินใจจะนั่งแท็กซี่ไปบ้านคุณยายที่อาศัยอยู่ในเมือง $N$ ในประเทศ IOI มีบริษัทแท็กซี่ $N$ แห่งตั้งแต่บริษัทแท็กซี่ $1$ ถึงบริษัทแท็กซี่ $N$ บริษัทแท็กซี่ในประเทศ IOI มีกฎที่ค่อนข้างพิเศษดังต่อไปนี้:

• แท็กซี่ของบริษัทแท็กซี่ $i$ สามารถขึ้นได้เฉพาะที่เมือง $i$ เท่านั้น
• ค่าโดยสารแท็กซี่ของบริษัทแท็กซี่ $i$ คือ $C_i$ โดยไม่ขึ้นกับระยะทางที่ใช้บริการ
• แท็กซี่ของบริษัทแท็กซี่ $i$ สามารถวิ่งผ่านถนนติดต่อกันได้สูงสุดไม่เกิน $R_i$ สายหลังจากขึ้นรถ

ตัวอย่างเช่น ในกรณีที่ $R_1 = 2$ หากขึ้นแท็กซี่ของบริษัทแท็กซี่ $1$ จากเมือง $1$ จะสามารถวิ่งผ่านถนนได้สูงสุดเพียง $2$ สาย ดังนั้นหากต้องการวิ่งผ่านถนนตั้งแต่ $3$ สายขึ้นไป จะต้องเปลี่ยนไปขึ้นแท็กซี่คันอื่นที่เมืองระหว่างทาง

JOI-kun ไม่สามารถขึ้นหรือลงแท็กซี่ในจุดอื่นที่ไม่ใช่เมืองได้ และไม่สามารถใช้วิธีการเดินทางอื่นนอกเหนือจากแท็กซี่ได้ จงเขียนโปรแกรมเพื่อหาค่าต่ำสุดของผลรวมค่าโดยสารที่จำเป็นเพื่อให้ JOI-kun เดินทางไปถึงเมือง $N$

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วย $1 + N + K$ บรรทัด

บรรทัดที่ $1$ มีจำนวนเต็ม $2$ จำนวนคือ $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$) คั่นด้วยช่องว่าง แสดงว่าประเทศ IOI ประกอบด้วยเมือง $N$ เมือง และจำนวนถนนในประเทศ IOI คือ $K$ สาย

บรรทัดที่ $i$ ($1 \le i \le N$) จาก $N$ บรรทัดถัดมามีจำนวนเต็ม $2$ จำนวนคือ $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$) คั่นด้วยช่องว่าง แสดงว่าค่าโดยสารแท็กซี่ของบริษัทแท็กซี่ $i$ คือ $C_i$ และสามารถวิ่งผ่านถนนติดต่อกันได้สูงสุดไม่เกิน $R_i$ สายหลังจากขึ้นรถ

บรรทัดที่ $j$ ($1 \le j \le K$) จาก $K$ บรรทัดถัดมามีจำนวนเต็มที่แตกต่างกัน $2$ จำนวนคือ $A_j, B_j$ ($1 \le A_j < B_j \le N$) คั่นด้วยช่องว่าง แสดงว่ามีถนนเชื่อมระหว่างเมือง $A_j$ กับเมือง $B_j$ และจะไม่มีคู่ $(A_j, B_j)$ เดียวกันปรากฏตั้งแต่ $2$ ครั้งขึ้นไป

ในข้อมูลนำเข้าที่กำหนดให้ รับประกันว่าสามารถเดินทางจากเมืองใดๆ ไปยังเมืองอื่นใดๆ ได้ด้วยการต่อรถแท็กซี่

ข้อมูลส่งออก

แสดงจำนวนเต็มที่แทนค่าต่ำสุดของผลรวมค่าโดยสารที่จำเป็นสำหรับ JOI-kun ในการเดินทางจากเมือง $1$ ไปยังเมือง $N$ ใน $1$ บรรทัด

ตัวอย่าง

ข้อมูลนำเข้า 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

ข้อมูลส่งออก 1

700

หมายเหตุ

ตัวอย่างข้างต้นสอดคล้องกับแผนภาพด้านล่าง วงกลมแทนเมือง และเส้นตรงแทนถนน

ในตัวอย่างนี้ การที่ JOI-kun จะเดินทางไปยังเมือง $6$ ด้วยค่าโดยสารน้อยที่สุด สามารถทำได้ดังนี้:

• ขึ้นแท็กซี่จากเมือง $1$ ไปยังเมือง $5$ (ค่าโดยสาร $400$)
• ขึ้นแท็กซี่จากเมือง $5$ ไปยังเมือง $6$ (ค่าโดยสาร $300$)

เมื่อ JOI-kun เดินทางตามเส้นทางดังกล่าว ผลรวมค่าโดยสารจะเท่ากับ $400 + 300 = 700$ ดังนั้นจึงแสดงผลเป็น $700$