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 INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 100007;
struct eT {
  void setd(int _u, int _v, int _w, int _l) {
    u = _u, v = _v, w = _w, last = _l;
  }
  int u, v, w, last;
} edge[MAXN];
struct qT {
  void setd(int _ni, int _nxt) { ni = _ni, nxt = _nxt; }
  int ni, nxt;
} que[MAXN * 2];
struct pqT {
  pqT() : id(0), dist(0) {}
  pqT(int _id, long long _dist) : id(_id), dist(_dist) {}
  bool operator<(const pqT &a) const { return dist > a.dist; }
  int id;
  long long dist;
};
int n, m, q;
int ke, la[MAXN];
int kq, lq[MAXN], rq[MAXN];
long long ad[MAXN], dist[MAXN];
int ew[MAXN];
bool vis[MAXN];
int qtp, qa;
int ql[MAXN];
bool cg[MAXN];
void init();
void input();
void inputq();
void work();
int main() {
  init();
  input();
  work();
}
void init() { ios::sync_with_stdio(false); }
void input() {
  scanf("%d%d%d", &n, &m, &q);
  int u, v, w;
  ke = 1;
  memset(la, -1, sizeof(la));
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    edge[ke].setd(u, v, w, la[u]);
    la[u] = ke++;
    ew[i] = w;
  }
}
void inputq() {
  scanf("%d", &qtp);
  if (qtp == 1)
    scanf("%d", &qa);
  else {
    scanf("%d", &qa);
    for (int i = 1; i <= qa; ++i) scanf("%d", &ql[i]);
  }
}
void work() {
  priority_queue<pqT> pq;
  memset(dist, 0x3f3f3f3f, sizeof(dist));
  dist[1] = 0;
  pq.push(pqT(1, 0));
  int now, v;
  while (!pq.empty()) {
    now = pq.top().id;
    pq.pop();
    if (vis[now]) continue;
    vis[now] = true;
    for (int i = la[now]; ~i; i = edge[i].last) {
      if (dist[v = edge[i].v] > dist[now] + edge[i].w) {
        dist[v] = dist[now] + edge[i].w;
        pq.push(pqT(v, dist[v]));
      }
    }
  }
  memset(cg, true, sizeof(cg));
  for (int i = 1; i <= n; ++i) {
    ad[i] = dist[i];
    if (dist[i] == dist[0]) cg[i] = false;
  }
  for (int i = 0; i <= n; ++i) lq[i] = i;
  for (int _q = 0; _q < q; ++_q) {
    inputq();
    if (qtp == 1)
      printf("%I64d\n", cg[qa] ? ad[qa] : -1);
    else {
      for (int i = 1; i <= qa; ++i) ++ew[ql[i]];
      for (int i = 0; i <= n; ++i) rq[i] = lq[i];
      kq = n;
      for (int i = 1; i <= m; ++i)
        edge[i].w = ew[i] - (ad[edge[i].v] - ad[edge[i].u]);
      memset(dist, 0x3f3f3f3f, sizeof(dist));
      dist[1] = 0;
      que[rq[0]].nxt = ++kq;
      que[kq].ni = 1;
      rq[0] = kq;
      memset(vis, false, sizeof(vis));
      for (int i = 0; i <= n; ++i) {
        for (int j = lq[i]; j ^ rq[i];) {
          j = que[j].nxt;
          now = que[j].ni;
          if (vis[now]) continue;
          vis[now] = true;
          for (int k = la[now]; ~k; k = edge[k].last) {
            if (dist[v = edge[k].v] > dist[now] + edge[k].w) {
              dist[v] = dist[now] + edge[k].w;
              if (dist[v] <= n) {
                que[rq[dist[v]]].nxt = ++kq;
                que[kq].ni = v;
                rq[dist[v]] = kq;
              }
            }
          }
        }
      }
      for (int i = 1; i <= n; ++i) ad[i] += dist[i];
    }
  }
}