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;
};
template <size_t NumHeaps, typename Entry>
struct Heaps {
  void Normalize() {
    if (empty()) return;
    while (m_heaps[m_curr].empty()) m_curr = (m_curr + 1) % NumHeaps;
  }
  template <typename... Args>
  void emplace(size_t heap, Args &&...args) {
    m_heaps[(m_curr + heap) % NumHeaps].emplace_back(
        std::forward<Args>(args)...);
    ++m_size;
  }
  Entry const &front() {
    Normalize();
    assert(!m_heaps[m_curr].empty());
    return m_heaps[m_curr].back();
  }
  void pop() {
    assert(!m_heaps[m_curr].empty());
    m_heaps[m_curr].pop_back();
    --m_size;
  }
  bool empty() const { return m_size == 0; }
  size_t size() const { return m_size; }
  array<vector<Entry>, NumHeaps> m_heaps;
  size_t m_curr = 0;
  size_t m_size = 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;
};
size_t const kNumHeaps = 128;
Heaps<kNumHeaps, State> g_small;
PriorityQueue<State> g_large;
void Dijkstra(Graph const &graph, vector<int64_t> const &oldDistance,
              vector<int64_t> &newDistance) {
  newDistance.assign(graph.NumVertices(), -1);
  newDistance[0] = 0;
  g_small.emplace(0, newDistance[0], 0);
  while (!g_small.empty() || !g_large.empty()) {
    if (g_small.empty()) {
      auto const state = g_large.top();
      g_large.pop();
      g_small.emplace(0, state);
      while (!g_large.empty() &&
             g_large.top().m_distance < state.m_distance + kNumHeaps) {
        auto const s = g_large.top();
        g_large.pop();
        g_small.emplace(s.m_distance - state.m_distance, s);
      }
      continue;
    }
    assert(!g_small.empty());
    auto const state = g_small.front();
    g_small.pop();
    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 < kNumHeaps)
          g_small.emplace(weight, ndistance, edge.m_to);
        else
          g_large.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;
}