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>
const int S = 1 << 21;
char ibuf[S], *iS, *iT, obuf[S], *oS = obuf, *oT = oS + S - 1;
struct Flusher_ {
  ~Flusher_() { (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void()); }
} flusher_;
template <class T>
inline void read(T &x) {
  x = 0;
  register char c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, S, stdin),
                                 (iS == iT ? EOF : *iS++))
                              : *iS++);
  register bool f = 0;
  while (!isdigit(c))
    f ^= c == '-', c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, S, stdin),
                                    (iS == iT ? EOF : *iS++))
                                 : *iS++);
  while (isdigit(c))
    x = x * 10 + c - '0',
    c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, S, stdin),
                     (iS == iT ? EOF : *iS++))
                  : *iS++);
  if (f) x = -x;
}
template <class T>
inline void print(T x) {
  if (x < 0)
    (*oS++ = ('-'),
     oS == oT ? (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void())
              : void()),
        x = -x;
  if (x > 9) print(x / 10);
  (*oS++ = (x % 10 + '0'),
   oS == oT ? (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void()) : void());
}
template <class T>
inline void print(T x, char c) {
  print(x), (*oS++ = (c),
             oS == oT ? (fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void())
                      : void());
}
template <class T>
inline void setmin(T &x, T y) {
  if (y < x) x = y;
}
const int N = 1e5 + 10, M = 2e3 + 10;
int n, m, k, same;
bool vis[N];
long long dis[N];
std::tuple<int, int, int, size_t> e[N];
std::vector<std::pair<int, int>> G[N];
struct Query {
  int o, c;
  std::vector<int> v;
} q[M];
struct RadixHeap {
  static const int bit = 64;
  static const long long inf = std::numeric_limits<long long>::max();
  RadixHeap() : sz(0), last(0) { std::fill(vm, vm + bit + 1, inf); }
  static inline int pos(long long x) {
    return !x ? 0 : 64 - __builtin_clzll(x);
  }
  inline void push(long long x, int y) {
    const auto vi = pos(x ^ last);
    v[vi].emplace_back(x, y), ++sz;
    setmin(vm[vi], x);
  }
  inline std::pair<long long, int> pop() {
    const auto ret = get();
    v[0].pop_back(), --sz;
    return ret;
  }
  inline std::pair<long long, int> top() { return get(); }
  std::pair<long long, int> get() {
    if (v[0].empty()) {
      int i = 1;
      while (v[i].empty()) ++i;
      last = vm[i];
      for (const auto &p : v[i]) {
        const auto vi = pos(p.first ^ last);
        v[vi].emplace_back(p);
        setmin(vm[vi], p.first);
      }
      v[i].clear(), vm[i] = inf;
    }
    return v[0].back();
  }
  inline bool empty() const { return !sz; }
  inline int size() const { return sz; }
  std::vector<std::pair<long long, int>> v[bit + 1];
  long long last, vm[bit + 1];
  int sz;
};
void dij() {
  if (same) return;
  same = true;
  memset(vis, 0, sizeof(vis));
  memset(dis, 63, sizeof(dis));
  dis[1] = 0;
  RadixHeap q;
  q.push(0, 1);
  while (q.size()) {
    int u = q.pop().second;
    if (vis[u]) continue;
    vis[u] = true;
    for (const auto &e : G[u])
      if (dis[u] + e.second < dis[e.first]) {
        dis[e.first] = e.second + dis[u];
        q.push(dis[e.first], e.first);
      }
  }
}
int main() {
  read(n), read(m), read(k);
  for (int u, v, w, i = 1; i <= m; i++) {
    read(u), read(v), read(w);
    e[i] = {u, v, w, G[u].size()};
    G[u].push_back({v, w});
  }
  int cnt = 0;
  for (int i = 1; i <= k; i++) {
    read(q[i].o), read(q[i].c);
    if (q[i].o == 2) {
      q[i].v.resize(q[i].c);
      for (int j = 0; j < q[i].c; j++) read(q[i].v[j]);
    }
    cnt += q[i].o == 1;
  }
  bool flag = cnt <= (k >> 1);
  dij();
  for (int i = 1; i <= k; i++)
    if (q[i].o == 1) {
      if (flag) dij();
      print(dis[q[i].c] > 1e18 ? -1 : dis[q[i].c], '\n');
    } else {
      same = false;
      for (int l : q[i].v) {
        G[std::get<0>(e[l])][std::get<3>(e[l])].second++;
      }
      if (!flag) dij();
    }
}