신제품 개발

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\le K\le 10^{18}$
• $0\le A_i\le 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\le B_i\le 10^{18}$ ($1\le i\le M$)
• $B_1,\cdots,B_M$은 서로 다릅니다.