킹십리역 갓번 출구

영민이의 멘토링 조는 항상 킹십리역 $G$번 출구에서 만나기로 약속 장소를 정한다. 하지만 킹십리역은 구조가 매우 복잡하기 때문에 $G$번 출구를 찾아가기란 쉽지 않다.

킹십리역은 각각의 출구를 정점으로 하고, 두 출구 사이의 통로 구간을 간선으로 하는 하나의 그래프로 나타낼 수 있다. 서로 다른 두 출구는 최대 1개의 통로 구간으로 연결되며, 임의의 두 출구 사이에 이동 가능한 경로가 반드시 존재한다. 영민이는 특정 출구에서 매번 $G$번 출구를 찾아가면서 킹십리역 내부 구조를 학습한다.

특정 출구에서 $G$번 출구로 찾아가는 경로는 여러 통로 구간으로 구성될 수 있다. 그런데 영민이는 특정 경로를 한 번 이용하면 그 경로에 너무 익숙해진 나머지, 해당 경로를 구성하지 않는 모든 통로 구간의 헷갈리는 정도가 일정량 증가한다. 처음에 모든 통로 구간의 헷갈리는 정도는 $0$이며, 각 구간을 이동하는 데 걸리는 시간은 해당 구간의 길이와 헷갈리는 정도의 합과 같다.

영민이가 $G$번 출구를 찾아갈 때는 다음과 같은 규칙을 순서대로 따른다.

1. 각 통로 구간에서 헷갈리는 정도의 최댓값이 더 작은 경로를 이용한다.
2. 각 통로 구간 길이의 총합이 더 짧은 경로를 이용한다.
3. 더 적은 출구를 경유하는 경로를 이용한다.
4. 경로상의 출구 번호를 경유하는 순서대로 나열할 때, 사전 순으로 더 빠른 수열을 가진 경로를 이용한다.

출구들의 정보가 주어질 때, 다음과 같은 질의를 수행하는 프로그램을 작성하시오.

• $1$ $i$ $v$: $i$번 출구에서 $G$번 출구까지 이동하며 경로를 학습한다. (경로를 구성하지 않는 각 통로 구간의 헷갈리는 정도가 $v$만큼 증가한다.)
• $2$ $i$: $i$번 출구에서 $G$번 출구까지 이동한다고 가정할 때 걸리는 시간을 출력한다. (학습하는 과정이 아니므로 각 통로 구간의 헷갈리는 정도에는 변화가 없다.)

첫 번째 줄에 출구의 개수 $N$과 두 출구 사이를 연결하는 통로 구간의 개수 $M$, $G$가 공백으로 구분되어 주어진다. $(2 \le N \le 100\,000,\ N-1 \le M \le \min(10^6, \frac{N(N-1)}{2}),\ 1 \le G \le N)$

두 번째 줄부터 $M$개의 줄에 각 통로의 양 끝 출구의 번호 $a, b$와 통로 구간의 길이 $d$가 주어진다. 모든 통로 구간의 길이는 정수이다. $(1 \le a, b \le N,\ a ≠ b, 1 \le d \le 10\,000)$

$M+2$ 번째 줄에 질의의 개수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$

$M+3$ 번째 줄부터 $Q$개의 줄에 문제에서 설명한 형태의 질의가 한 줄에 하나씩 주어진다. $(1 \le i \le N,$ $i \ne G,$ $1 \le v \le 10\,000)$

1번 질의에서 $v$의 값은 항상 정수이고, 2번 질의는 1개 이상 주어진다.

2번 질의에 대해 한 줄에 하나씩 $i$번 출구에서 $G$번 출구까지 이동한다고 가정할 때 걸리는 시간을 출력한다.