31566번 - 힘세고 강한 아침

문제

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

나는 영도

근성은 매일 아침 개발 문서를 읽으며 하루를 시작한다. 한국어 문서를 다 읽은 근성은 해외 문서를 읽기 시작했지만, 세상의 다양한 언어로 작성된 개발 문서를 보고 눈앞이 아득해지기 시작했다. 이를 본 영도는 근성을 도와주고자 $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$는 수이다.
• 입력으로 주어지는 모든 수는 정수이다.

힌트