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;
int n, i, j, k, x, y, w, m, Q, used[100500], start;
int a[100500], b[100500], c[100500];
vector<pair<int, int> > g[100500];
vector<int> f[100500];
long long d[100500];
long long hea[200500];
int new_w[100500], new_d[100500];
int hea2[200500];
int st[100500], sz[100500], cur_pos[100500];
int G[100500];
int heapSize;
void add(pair<long long, int> value) {
  hea[heapSize++] = value.first;
  int i = heapSize - 1;
  hea2[i] = value.second;
  int parent = ((i - 1) >> 1);
  while (i > 0 && hea[parent] < hea[i]) {
    swap(hea[i], hea[parent]);
    swap(hea2[i], hea2[parent]);
    i = parent;
    parent = ((i - 1) >> 1);
  }
}
void heapify(int i) {
  int largestChild;
  for (;;) {
    largestChild = i;
    if (hea[2 * i + 1] > hea[largestChild]) {
      largestChild = 2 * i + 1;
    }
    if (hea[2 * i + 2] > hea[largestChild]) {
      largestChild = 2 * i + 2;
    }
    if (largestChild == i) {
      break;
    }
    swap(hea[i], hea[largestChild]);
    swap(hea2[i], hea2[largestChild]);
    i = largestChild;
  }
}
pair<long long, int> getMax() {
  pair<int, int> result = make_pair(hea[0], hea2[0]);
  heapSize--;
  hea[0] = hea[heapSize];
  hea2[0] = hea2[heapSize];
  hea[heapSize] = -(long long)1e+18;
  heapify(0);
  return result;
}
inline unsigned int readUInt() {
  int c = getc(stdin);
  unsigned int x = 0;
  while (c <= 32) c = getc(stdin);
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getc(stdin);
  return x;
}
int main() {
  cin >> n >> m >> Q;
  for (i = 0; i <= 200000; i++) hea[i] = -(long long)1e+18;
  for (i = 0; i < m; i++) {
    int x, y, z;
    a[i] = readUInt();
    b[i] = readUInt();
    c[i] = readUInt();
  }
  int s = 1;
  for (i = 0; i < m; i++) {
    g[a[i]].push_back(make_pair(b[i], c[i]));
  }
  st[1] = 0;
  sz[1] = g[1].size();
  for (i = 2; i <= n; i++) {
    st[i] = cur_pos[i] = st[i - 1] + g[i - 1].size();
    sz[i] = g[i].size();
  }
  for (i = 0; i < m; i++) {
    G[cur_pos[a[i]]++] = i;
  }
  for (i = 1; i <= n; i++) d[i] = (long long)1e+18;
  d[s] = 0;
  for (i = 0; i < heapSize; i++) hea[i] = -(long long)1e+18;
  heapSize = 0;
  add(make_pair(0, s));
  while (heapSize) {
    pair<int, int> tmp = getMax();
    int v = tmp.second;
    long long cur_d = -tmp.first;
    if (cur_d > d[v]) continue;
    for (size_t j = 0; j < g[v].size(); ++j) {
      int to = g[v][j].first;
      long long len = g[v][j].second;
      if (d[v] + len < d[to]) {
        d[to] = d[v] + len;
        add(make_pair(-d[to], to));
      }
    }
  }
  for (i = 0; i < m; i++) new_w[i] = min(100000000LL, c[i] + d[a[i]] - d[b[i]]);
  for (int ii = 0; ii < Q; ii++) {
    int test;
    cin >> test;
    if (test == 1) {
      int t;
      cin >> t;
      if (d[t] == (long long)1e+18)
        cout << -1 << endl;
      else
        cout << d[t] << endl;
    } else {
      cin >> x;
      for (i = 0; i < x; i++) {
        int y = readUInt();
        new_w[y - 1]++;
        c[y - 1]++;
      }
      for (i = 0; i <= n; i++) {
        f[i].clear();
        new_d[i] = (int)1e+9;
      }
      f[0].push_back(1);
      new_d[1] = 0;
      for (i = 0; i <= x; i++) {
        for (j = 0; j < f[i].size(); j++) {
          int v = f[i][j];
          if (new_d[v] == i) {
            int tmp = st[v] + sz[v];
            for (k = st[v]; k < tmp; k++) {
              int to = b[G[k]];
              int val = new_w[G[k]];
              if (new_d[to] > i + val) {
                new_d[to] = min(100000000, i + val);
                if (new_d[to] <= x) f[new_d[to]].push_back(to);
              }
            }
          }
        }
      }
      for (i = 1; i <= n; i++) {
        d[i] += new_d[i];
        if (d[i] > (long long)1e+18) d[i] = (long long)1e+18;
      }
      for (i = 0; i < m; i++)
        new_w[i] = min(100000000LL, c[i] + d[a[i]] - d[b[i]]);
    }
  }
  return 0;
}