힘세고 강한 아침

안녕하신가! 힘세고 강한 아침, 만일 내게 물어보면

나는 영도

근성은 매일 아침 개발 문서를 읽으며 하루를 시작한다. 한국어 문서를 다 읽은 근성은 해외 문서를 읽기 시작했지만, 세상의 다양한 언어로 작성된 개발 문서를 보고 눈앞이 아득해졌다. 이를 본 영도는 근성을 도와주려고 '정영도 봇'(이하 봇)을 만들었다. 봇은 $N$개 언어 가운데 일부 언어 쌍에 대한 번역을 제공한다.

봇은 프로토타입이라 특이한 번역 로직을 가지고 있다.

• 각 언어는 $1$ 이상 $N$ 이하의 중복되지 않는 고유 번호를 가진다.
• 봇은 일부 $(A,B)$ 언어 쌍에 대한 데이터를 가지고 있다. 여기서 $A$와 $B$는 언어의 고유 번호다.
• 변환은 어떤 언어로 쓰인 문구를 다른 언어로 쓰인 문구로 바꾸는 과정이다. $A$번 언어의 문구를 $B$번 언어의 문구로 바꾸려면 봇이 $(A,B)$ 언어 쌍에 대한 데이터를 가지고 있어야 한다. $(A,B)$와 $(B,A)$는 서로 다른 언어 쌍이다.
• '$A$번 언어의 문구를 $B$번 언어의 문구로 바꾸는 변환'은 '$A$번 언어를 $B$번 언어로 바꾸는 변환'으로 줄여 쓸 수 있다.
• 변환에는 비용이 든다.
• $A$번 언어를 $B$번 언어로 번역하는 것은 한 번 이상의 변환을 거쳐 $A$번 언어를 $B$번 언어로 바꾸는 것이다. 이 과정에서 거치는 변환의 순서를 경로라고 한다.

근성은 봇의 성능을 확인하려고, 언어 $s$가 있을 때 특정 언어 $k$를 거치지 않고 언어 $e$로 번역할 수 있는지 묻고, 가능하다면 경로들의 비용 중 최솟값이 얼마인지 여러 번 물었다. 영도는 질문에 답하려고 입력값을 하나씩 넣는 일에 지쳤다. 그래서 번역 가능 여부와 최소 비용을 구하는 프로그램을 만들려 했지만, 봇을 만드는 데 힘을 너무 많이 써서 또 다른 프로그램을 만들 힘이 남지 않았다.

영도를 위해 봇의 번역 가능 여부와 최소 비용을 구하는 프로그램을 작성하라.

첫 번째 줄에 언어의 개수 $N$, 봇이 가진 데이터의 개수 $M$, 질문의 개수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 $b$ $t$ $c$ 형식으로 데이터가 주어진다. 봇이 $(b,t)$ 언어 쌍에 대한 데이터를 가지고 있고, 그 언어 쌍을 이용한 변환의 비용이 $c$라는 뜻이다. 봇은 같은 $(b,t)$ 언어 쌍에 대한 데이터를 중복으로 가지지 않는다.

$M+2$번째 줄부터 $Q$개의 줄에 걸쳐 $s$ $k$ $e$ 형식으로 질문이 주어진다. 언어 $s$가 있을 때, 언어 $k$를 포함하는 변환을 거치지 않고 언어 $e$로 번역할 수 있는지, 가능하다면 경로들의 비용 중 최솟값이 얼마인지 묻는 질문이다.

각 질문에 대해 번역이 가능하면 경로들의 비용 중 최솟값을, 불가능하면 No를 한 줄에 하나씩 출력한다.

• $3 \le N \le 100$
• $1 \le M \le N \times (N-1)$
• $1 \le Q \le 200\,000$
• $b \neq t$; $1 \le b, t \le N$; $1 \le c \le 10\,000$
• $s \neq e$; $s \neq k$; $e \neq k$; $1 \le s, k, e \le N$
• 입력으로 주어지는 $N$, $M$, $Q$, $b$, $t$, $c$, $s$, $k$, $e$는 모두 정수이다.