Dịch vụ truyền thông

Công ty cung cấp dịch vụ mạng HDS vừa thiết lập một mạng truyền thông, mạng bao gồm $n$ nút và $m$ kênh nối trực tiếp một chiều giữa hai nút. Các nút được đánh số từ $1$ đến $n$, các kênh nối được đánh số từ $1$ đến $m$. Kênh nối thứ $i$ cho phép truyền tin (một chiều) từ nút $u_i$ tới nút $v_i$ và có độ trễ là $c(u_i,v_i)$. Có không quá một kênh truyền tin từ một nút đến một nút khác. Một đường truyền tin từ nút $s$ đến nút $t$ được biểu diễn dưới dạng một dãy liên tiếp các chỉ số của các nút, xuất phát từ $s$ và kết thúc tại $t$. Độ trễ của đường truyền tin được định nghĩa là tổng độ trễ của các kênh nối trực tiếp trên đường truyền tin đó.

Để đánh giá mạng truyền thông, công ty đưa ra kịch bản kiểm tra như sau: Ban đầu tất cả $n$ nút đều ở chế độ không chuyển tiếp tin; có $k$ thao tác thuộc một trong hai loại sau:

• Loại $1$, nhận một chỉ số $x$ ($1\le x\le n$) có ý nghĩa: kích hoạt nút $x$ sang chế độ được chuyển tiếp tin (kích hoạt một nút đã được kích hoạt thì không có thay đổi gì);
• Loại $2$, nhận hai chỉ số $x,y$ ($1\le x,y\le n$) có ý nghĩa: cần tính độ trễ của đường truyền tin từ nút $x$ đến nút $y$ (không đi qua nút ở chế độ không chuyển tiếp tin) có độ trễ nhỏ nhất, nếu không tồn tại đường truyền thì đưa ra $-1$.

Điều kiện "không đi qua nút ở chế độ không chuyển tiếp tin" chỉ áp dụng cho các nút trung gian của đường truyền: hai nút đầu $x$ và cuối $y$ không cần được kích hoạt. Khi $x=y$, đường truyền chỉ gồm một nút $x$ và có độ trễ bằng $0$.

Yêu cầu: Cho biết mạng truyền thông của công ty HDS và kịch bản kiểm tra gồm $k$ thao tác, hãy thực hiện lần lượt từng thao tác và với mỗi thao tác loại $2$ thì đưa ra độ trễ nhỏ nhất cần tính.

Dữ liệu vào

• Dòng đầu tiên chứa $3$ số nguyên dương $n,m,k$.
• Dòng thứ $i$ trong số $m$ dòng tiếp theo ghi ba số nguyên dương $u_i,v_i,c(u_i,v_i)$ lần lượt là chỉ số đầu, chỉ số cuối và độ trễ của kênh thứ $i$ ($u_i\ne v_i$). Độ trễ của các kênh là nhỏ hơn ${10}^9$.
• $k$ dòng tiếp theo mô tả kịch bản, cụ thể:
  • Nếu thao tác thứ $j$ thuộc loại $1$ thì dòng thứ $j$ gồm $2$ số, số thứ nhất bằng $1$ và số thứ hai là chỉ số nút;
  • Nếu thao tác thứ $j$ thuộc loại $2$ thì dòng thứ $j$ gồm $3$ số, số thứ nhất bằng $2$ và hai số sau là hai chỉ số nút.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

Gồm một số dòng, mỗi dòng là câu trả lời cho thao tác loại $2$ xuất hiện lần lượt trong kịch bản.

Ràng buộc

• $2\le n\le 500$; $1\le m\le n(n-1)$; $1\le k\le {10}^6$.
• $1\le u_i,v_i\le n$, $u_i\ne v_i$; không có hai kênh cùng đi từ một nút đến cùng một nút.
• $1\le c(u_i,v_i)<{10}^9$.
• Kịch bản có ít nhất một thao tác loại $2$.

Subtasks

• Subtask 1 ($20$ điểm): $n\le 10$, $k\le 10$.
• Subtask 2 ($20$ điểm): $n\le 100$, $k\le {10}^2$.
• Subtask 3 ($30$ điểm): $n\le 500$, $k\le {10}^6$.

Ví dụ