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;
const int Imx = 2147483647;
const long long Lbig = 2e18;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c == ' ' || c == '\n') c = _buff.get();
  return c;
}
int n, m, q;
int head[100111], nxt[100111], to[100111], w[100111], tot;
int dis2[100111];
bool vis[100111];
set<pair<long long, int> > st;
long long dis[100111];
void prework() {
  for (int i = 2; i <= n; i++) dis[i] = Lbig;
  st.clear();
  st.insert(make_pair(0, 1));
  dis[1] = 0;
  memset(vis, 0, sizeof(vis));
  while (st.size() > 0) {
    int u = st.begin()->second;
    st.erase(st.begin());
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
      if (dis[u] + w[i] < dis[to[i]]) {
        dis[to[i]] = dis[u] + w[i];
        st.insert(make_pair(dis[to[i]], to[i]));
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i]) {
      for (int j = head[i]; j; j = nxt[j]) {
        w[j] -= dis[to[j]] - dis[i];
      }
    }
  }
}
vector<int> v[1000111];
void update() {
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i <= m; i++) v[i].clear();
  for (int i = 1; i <= n; i++) dis2[i] = mod;
  v[0].push_back(1);
  dis2[1] = 0;
  for (int i = 0; i <= m; i++) {
    for (int it = 0; it < v[i].size(); it++) {
      int u = v[i][it];
      if (vis[u]) continue;
      vis[u] = 1;
      for (int j = head[u]; j; j = nxt[j]) {
        if (i + w[j] < min(m + 1, dis2[to[j]]) && !vis[to[j]]) {
          v[i + w[j]].push_back(to[j]);
          dis2[to[j]] = i + w[j];
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i]) {
      for (int j = head[i]; j; j = nxt[j]) {
        w[j] -= dis2[to[j]] - dis2[i];
      }
    }
  }
  for (int i = 1; i <= n; i++)
    if (dis2[i] != mod) dis[i] += dis2[i];
  m = 0;
}
int main() {
  n = getnum(), m = getnum(), q = getnum();
  for (int i = 1; i <= m; i++) {
    int x, y, c;
    x = getnum(), y = getnum(), c = getnum();
    nxt[++tot] = head[x];
    head[x] = tot;
    to[tot] = y;
    w[tot] = c;
  }
  m = 0;
  prework();
  for (int i = 1; i <= q; i++) {
    int cmd;
    cmd = getnum();
    if (cmd == 1) {
      int x;
      x = getnum();
      if (dis[x] == Lbig) {
        puts("-1");
      } else {
        update();
        putnum(dis[x]), putchar('\n');
      }
    } else {
      int k;
      k = getnum();
      m += k;
      while (k--) {
        int x;
        x = getnum();
        w[x]++;
      }
    }
  }
  return 0;
}