Xây dựng tuyến đường giao thông

Quốc gia $Z$ có $N$ thành phố được nối với nhau bởi $M$ con đường hai chiều và $K$ sân bay. Khi đi qua một con đường nối hai thành phố $U$ và $V$ $(1\le U,V\le N)$ bằng ô tô thì sẽ mất thời gian là $C$ phút. Mỗi thành phố có tối đa một sân bay và bất cứ chuyến bay nào (giữa hai thành phố có sân bay) đều có thời gian di chuyển mất $T$ phút.

Lãnh đạo quốc gia $Z$ đưa ra $Q$ yêu cầu để đẩy mạnh phát triển cơ sở hạ tầng. Yêu cầu sau chỉ được thực hiện khi yêu cầu trước đó đã hoàn thành. Mỗi yêu cầu của lãnh đạo có thể thực hiện một trong ba loại công việc sau:

• Loại $1$: Xây dựng một con đường hai chiều mới giữa hai thành phố $U$ và $V$ $(1\le U,V\le N)$ sao cho mất $C$ phút khi di chuyển bằng ô tô.
• Loại $2$: Xây dựng một sân bay mới ở một thành phố $X$ $(1\le X\le N)$.
• Loại $3$: Tính ${\displaystyle {\sum }_{i=1}^N{\sum }_{j=1}^{N}F(i,j)}$ với $F(i,j)$ là tổng thời gian tối thiểu để đi từ thành phố $i$ đến thành phố $j$ qua các con đường và chuyến bay (nếu không có cách đi hoặc $i=j$ thì $F(i,j)=0$).

Yêu cầu: Bạn hãy giúp lãnh đạo mô hình hóa các yêu cầu loại $1$ và $2$, cho biết kết quả của các yêu cầu loại $3$ tương ứng.

Dữ liệu vào

• Dòng đầu tiên chứa năm số nguyên $N,M,Q,K,T$ $(1\le N,Q\le 400;0\le K\le N;1\le M\le {10}^5;1\le T\le {10}^9)$.
• Dòng thứ hai gồm $K$ số nguyên đôi một phân biệt $A_1,A_2,\dots ,A_K$ cho biết các thành phố có sân bay $(1\le A_i\le N)$; dòng này để trống nếu $K=0$.
• $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $U,V,C$ cho biết có con đường nối hai thành phố $U$ và $V$ với thời gian di chuyển bằng ô tô là $C$ phút $(1\le U,V\le N;U\ne V;1\le C\le {10}^9)$.
• $Q$ dòng cuối cùng, mỗi dòng được viết theo một trong ba định dạng tương ứng với ba loại yêu cầu:
  • Loại $1$: 1 X Y C, tức xây dựng một con đường mới nối hai thành phố $X$ và $Y$ với thời gian di chuyển bằng ô tô là $C$ phút $(1\le X,Y\le N;X\ne Y;1\le C\le {10}^9)$.
  • Loại $2$: 2 X, tức xây dựng một sân bay mới tại thành phố $X$ $(1\le X\le N)$. Dữ liệu đảm bảo thành phố $X$ chưa có sân bay trước yêu cầu này.
  • Loại $3$: 3, tức yêu cầu tìm tổng thời gian tối thiểu.

Dữ liệu ra

Với mỗi yêu cầu loại $3$, ghi một số nguyên trên một dòng là kết quả tương ứng.

Ràng buộc

• $1\le N,Q\le 400$, $0\le K\le N$, $1\le M\le {10}^5$
• $1\le T,C\le {10}^9$

Subtasks

• Subtask 1 ($10\%$ số điểm): $N,Q\le 100$; $M\le 200$; $K=0$ và không có yêu cầu loại $2$.
• Subtask 2 ($20\%$ số điểm): $N,Q\le 100$.
• Subtask 3 ($30\%$ số điểm): $K=0$ và không có yêu cầu loại $2$.
• Subtask 4 ($40\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ