題目描述

小明喜歡觀景，于是今天他來到了藍橋公園。

已知公園有?N?個景點，景點和景點之間一共有?M條道路。小明有?Q個觀景計劃，每個計劃包含一個起點?st和一個終點?ed，表示他想從?stst?去到?ed。但是小明的體力有限，對于每個計劃他想走最少的路完成，你可以幫幫他嗎？

輸入描述

輸入第一行包含三個正整數(shù)?N,M,Q

第?2?到?M + 1?行每行包含三個正整數(shù)?u,v,w表示 vu?v?之間存在一條距離為?w?的路。

第?M+2?到?M + Q-1?行每行包含兩個正整數(shù)?st,ed，其含義如題所述。

輸出描述

輸出共?Q?行，對應(yīng)輸入數(shù)據(jù)中的查詢。

若無法從?st?到達?eded?則輸出??1。

輸入輸出樣例

示例 1

輸入

3 3 3?

1 2 1?

1 3 5

2 3 2?

1 2 1?

3 2 3

輸出

1?

3?

2

運行限制

語言 最大運行時間 最大運行內(nèi)存

C++ ???????? 1s ???? ???? 256M

?C ???????? ???? 1s ??????????256M

?Java ???? ???? 3s ?????????256M?

?Python3 ???? 50s ???? 256M

JAVA：

C/C++：