NC245487. Dynamic Shortest Path

描述

输入描述

第一行三个整数，
接下来行每行三个整数 , 表示第条边是连接且边权为的。
接下来行每行以一个开始描述一次询问。对于第类询问，保证所有的互不相同。
对于所有的第类询问涉及的边的数量总和不超过

输出描述

对于每一个第1类操作，输出一行一个整数表示最短路。如果最短路不存在，请输出-1。

示例1

输入:

3 2 9
1 2 0
2 3 0
2 1 2
1 3
1 2
2 1 1
1 3
1 2
2 2 1 2
1 3
1 2

输出:

1
0
2
1
4
2

示例2

输入:

5 4 9
2 3 1
2 4 1
3 4 1
1 2 0
1 5
1 4
2 1 2
2 1 2
1 4
2 2 1 3
1 4
2 1 4
1 4

输出:

-1
1
2
3
4

原站题解