Problem: You are given a weighted directed graph, consisting of n vertices and m edges. You should answer q queries of two types:

  * 1 v — find the length of shortest path from vertex 1 to vertex v. 
  * 2 c l1 l2 ... lc — add 1 to weights of edges with indices l1, l2, ..., lc. 

Input

The first line of input data contains integers n, m, q (1 ≤ n, m ≤ 105, 1 ≤ q ≤ 2000) — the number of vertices and edges in the graph, and the number of requests correspondingly.

Next m lines of input data contain the descriptions of edges: i-th of them contains description of edge with index i — three integers ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109) — the beginning and the end of edge, and its initial weight correspondingly.

Next q lines of input data contain the description of edges in the format described above (1 ≤ v ≤ n, 1 ≤ lj ≤ m). It's guaranteed that inside single query all lj are distinct. Also, it's guaranteed that a total number of edges in all requests of the second type does not exceed 106.

Output

For each query of first type print the length of the shortest path from 1 to v in a separate line. Print -1, if such path does not exists.

Examples

Input

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


Output

1
0
2
1
4
2


Input

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


Output

-1
1
2
3
4

Note

The description of changes of the graph in the first sample case:

<image>

The description of changes of the graph in the second sample case:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename State>
struct PriorityQueue {
  template <typename... Args>
  void emplace(Args &&...args) {
    m_heap.emplace_back(forward<Args>(args)...);
    push_heap(m_heap.begin(), m_heap.end(), m_comp);
  }
  bool empty() const { return m_heap.empty(); }
  State const &top() const { return m_heap.front(); }
  void pop() {
    pop_heap(m_heap.begin(), m_heap.end(), m_comp);
    m_heap.pop_back();
  }
  void clear() { m_heap.clear(); }
  vector<State> m_heap;
  greater<State> m_comp;
};
struct Edge {
  Edge() = default;
  Edge(int64_t weight, int from, int to)
      : m_weight(weight), m_from(from), m_to(to) {}
  int64_t m_weight = 0;
  int m_from = 0;
  int m_to = 0;
};
struct Graph {
  explicit Graph(int n) : m_adj(n) {}
  int NumVertices() const { return m_adj.size(); }
  void AddEdge(Edge const &edge) {
    assert(edge.m_from < m_adj.size());
    assert(edge.m_to < m_adj.size());
    m_adj[edge.m_from].push_back(m_edges.size());
    m_edges.push_back(edge);
  }
  void IncWeight(int edge) {
    assert(edge < m_edges.size());
    ++m_edges[edge].m_weight;
  }
  template <typename Fn>
  void ForEachOutgoingEdge(int u, Fn &&fn) const {
    for (int i : m_adj[u]) fn(m_edges[i]);
  }
  vector<vector<int>> m_adj;
  vector<Edge> m_edges;
};
struct State {
  State() = default;
  State(int64_t distance, int u) : m_distance(distance), m_u(u) {}
  bool operator>(State const &rhs) const { return m_distance > rhs.m_distance; }
  int64_t m_distance = 0;
  int m_u = 0;
};
vector<State> zero;
vector<State> one;
vector<State> two;
PriorityQueue<State> many;
void Dijkstra(Graph const &graph, vector<int64_t> const &oldDistance,
              vector<int64_t> &newDistance) {
  newDistance.assign(graph.NumVertices(), -1);
  newDistance[0] = 0;
  zero.emplace_back(newDistance[0], 0);
  while (!zero.empty() || !one.empty() || !two.empty() || !many.empty()) {
    State state;
    if (zero.empty() && one.empty() && two.empty()) {
      state = many.top();
      many.pop();
    } else {
      if (zero.empty()) {
        if (!one.empty()) {
          zero.swap(one);
          one.swap(two);
        } else {
          zero.swap(two);
        }
      }
      assert(!zero.empty());
      state = zero.back();
      zero.pop_back();
    }
    if (state.m_distance != newDistance[state.m_u]) continue;
    graph.ForEachOutgoingEdge(state.m_u, [&](Edge const &edge) {
      auto const weight =
          edge.m_weight + oldDistance[edge.m_from] - oldDistance[edge.m_to];
      auto const ndistance = state.m_distance + weight;
      if (newDistance[edge.m_to] < 0 || newDistance[edge.m_to] > ndistance) {
        newDistance[edge.m_to] = ndistance;
        if (weight == 0)
          zero.emplace_back(ndistance, edge.m_to);
        else if (weight == 1)
          one.emplace_back(ndistance, edge.m_to);
        else if (weight == 2)
          two.emplace_back(ndistance, edge.m_to);
        else
          many.emplace(ndistance, edge.m_to);
      }
    });
  }
  for (int i = 0; i < graph.NumVertices(); ++i) {
    if (oldDistance[i] >= 0) newDistance[i] += oldDistance[i];
  }
}
int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);
  Graph graph(n);
  for (int i = 0; i < m; ++i) {
    int weight;
    int from;
    int to;
    scanf("%d%d%d", &from, &to, &weight);
    --from, --to;
    graph.AddEdge(Edge(weight, from, to));
  }
  vector<int64_t> oldDistance(n, 0);
  vector<int64_t> newDistance(n, -1);
  bool dirty = true;
  for (int i = 0; i < q; ++i) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int v;
      scanf("%d", &v);
      if (dirty) {
        Dijkstra(graph, oldDistance, newDistance);
        oldDistance.swap(newDistance);
        dirty = false;
      }
      auto const d = static_cast<long long>(oldDistance[v - 1]);
      printf("%I64d\n", d);
    } else {
      assert(type == 2);
      int c, k;
      scanf("%d", &c);
      for (int j = 0; j < c; ++j) {
        scanf("%d", &k);
        graph.IncWeight(k - 1);
      }
      dirty = true;
    }
  }
  return 0;
}