언어별 시간/메모리

제약조건

1 ≤ T ≤ 100,000

2 ≤ N_t ≤ 200,000

0 ≤ M_t ≤ 500,000

번호가 붙은 정점의 개수의 합은 200,000을 넘지 않으며, 간선이나 다른 활자 그래프를 찍은 횟수의 합은 500,000을 넘지 않는다.

입력형식

첫 번째 줄에 활자 그래프의 개수 T가 주어진다.

이후, 각각의 활자 그래프에 대한 정보가 다음과 같이 주어진다.

• 현재 t번 활자 그래프를 입력받는다고 해보자.
• 첫 번째 줄에는 t번 활자 그래프의 번호가 붙은 정점의 개수 N_t와 간선이나 다른 활자 그래프를 찍은 횟수 M_t가 공백으로 구분되어 주어진다.
• 이후 M_t개의 줄에 걸쳐 3개의 정수 v,w,x가 공백으로 구분되어 주어진다. (1 ≤ v,w ≤ N_t; v ≠ w; −(t−1) ≤ x ≤ 10⁹)
  x ≥ 0이라면, 이는 v번 정점에서 w번 정점으로 가는 가중치 x의 단방향 간선을 찍었음을 의미한다.
  x < 0이라면, 이는 v번 정점을 시작점에 맞추고 w를 끝점에 맞춰서 |x|번 활자 그래프를 찍었음을 의미한다.

출력형식

첫 번째 줄에 T번 활자 그래프에서, 1번 정점에서 2번 정점으로 가는 최단 경로를 출력한다. 만약 1번 정점에서 2번 정점으로 가는 경로가 없거나, 이 값이 10¹⁸보다 크다면 −1을 대신 출력한다.

2
4 5
1 3 5
1 4 2
4 3 2
3 2 3
4 2 7
5 7
1 3 4
3 4 2
4 1 6
3 5 3
4 5 8
3 2 -1
5 2 7

11

1
2 1
2 1 1

-1

1
2 0

-1