D. Динамический кратчайший путь
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан взвешенный ориентированный граф, состоящий из n вершин и m ребер. Требуется ответить на q запросов двух типов:

  • 1 v — найти длину кратчайшего пути из вершины 1 в вершину v.
  • 2 c l1 l2 ... lc — прибавить 1 к весам ребер с номерами l1, l2, ..., lc.
Входные данные

Первая строка входных данных содержит целые числа n, m, q (1 ≤ n, m ≤ 105, 1 ≤ q ≤ 2000) — число вершин и ребер в графе и число запросов, соответственно.

Следующие m строк входных данных содержат описания ребер: в i-й из них находится описание ребра с номером i — три целых числа ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109) — начало ребра, конец ребра и его изначальный вес, соответственно.

Следующие q строк входных данных содержат описания запросов в вышеописанном формате (1 ≤ v ≤ n, 1 ≤ lj ≤ m). Гарантируется, что внутри одного запроса все lj различны, а также что суммарное число ребер в запросах второго типа не превосходит 106.

Выходные данные

Для каждого запроса первого типа выведите строку с одним числом — длиной кратчайшего пути от 1 до v, либо -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
Входные данные
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
Примечание

Иллюстрация изменений графа в первом примере из условия:

Иллюстрация изменений графа во втором примере из условия: