31250번 - 신제품 개발

FuriosaAI는 신세대 NPU (신경망 처리 단위) 제품을 만들어 당신이 AI 개발을 개척하는 데에 도움을 드립니다. 추론에 초점을 맞춘 NPU 제품은 비용과 에너지 소모량을 줄여 당신이 제약 없이 혁신할 수 있도록 할 것입니다.

FuriosaAI에서 일하는 연구원 주원이는 새로운 제품을 만들었다!

이 새로운 제품의 구성 요소는 다음과 같다.

• 제품에는 특수한 일을 하는 신경망의 구조가 이미 새겨져 있다. 신경망은 $N$개의 정점과 $M$개의 간선으로 이루어진 방향 그래프로 생각할 수 있다.
• 신경망 추론을 할 때, 우리가 관심이 있는 $u$번 정점과 카운터 $c$가 있다. 제품 가동 전에 $u=1$, $c=0$으로 초기화된다.
• 신경망의 $i$번 정점은 증분 $A_i$를 가지고 있다.
• 신경망의 $i$번 간선은 $u_i$번 정점에서 $v_i$번 정점으로 이으며, 두 정점은 서로 다르다.
• 신경망의 $i$번 간선은 특성값 $B_i$를 가지고 있는데, 그 값은 모두 다르다.

이 제품이 하는 일은 다음을 $K$번 반복하는 것이다.

1. 먼저 $u$번 정점에서 나가는 간선 중 $c\geq B_{i}$면서 $B_{i}$가 가장 큰 간선을 찾아 이를 $i$번 간선이라 하자.
   • $u$를 $v_{i}$로 업데이트한다. 즉, 우리의 시선을 $i$번 간선을 따라 ‘이동시켜’ 관심이 있는 정점을 바꾼다.
   • 그런 간선이 존재하지 않는다면 아무 것도 하지 않는다.
2. $c$의 값을 $c+A_{u}$로 업데이트한다.

연구원 주원이는 $1$초에 $10^{8}$번만 연산을 수행할 수 있다는 PSer들의 통념을 깨고, $K=10^{18}$일 때도 $1$초 만에 연산을 수행하여 초고속 승진을 노리려 한다. 여러분은 주원이의 계획을 도와야 한다!

첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $A_i$가 공백으로 구분되어 주어진다.

이후 $M$개의 줄에 걸쳐 $u_i$, $v_i$, $B_i$가 공백으로 구분되어 주어진다.

신제품이 연산 수행을 끝냈을 때 신제품의 상태인 $u$와 $c \bmod 1\,000\,000\,007$을 공백을 사이에 두고 출력한다.

• 주어지는 모든 수는 정수이다.
• $2\le N\le 500$
• $1\le M\le 100\, 000$
• $1\leq K\leq 10^{18}$
• $0\leq A_i\leq 10^{18}$ $(1\le i\le N)$
• $1\le u_i,v_i\le N$, $u_i\neq v_i$ $(1\le i\le M)$
• $(u_i,v_i)$ 쌍은 중복되어 주어질 수 있다.
• $0\leq B_i\leq 10^{18}$ $(1\le i\le M)$
• $B_1,\cdots ,B_M$은 서로 다르다.