1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct Graph {
  struct Edge {
    long distance;
  };
  struct Vertex : map< int, int > {
    int color;
    int marker;
    long distance;
    Vertex() : color(0), marker(0), distance(0) {
    }
  };
  vector< Vertex > V;
  vector< Edge > E;
  vector< int > Eunused;
  int marker;
  Graph(int n) : V(n), marker(0) {
  }
  int connect(int a, int b) {
    int eid;
    if (Eunused.size()) {
      eid = *Eunused.rbegin();
      Eunused.pop_back();
    } else
      E.resize((eid = E.size()) + 1);
    return V[b][a] = V[a][b] = eid;
  }
  void disconnect(int a, int b) {
    Vertex::iterator it = V[a].find(b);
    Eunused.push_back(it->second);
    V[a].erase(it);
    V[b].erase(a);
  }
  void color(int a, long d, int c) {
    vector< int > q(1, a);
    V[a].distance = 0;
    ++marker;
    for (int i = 0; i < (int)q.size(); ++i) {
      Vertex &u = V[q[i]];
      u.marker = marker;
      u.color = c;
      if (u.distance >= d)
        continue;
      for (Vertex::const_iterator it = u.begin(); it != u.end(); ++it) {
        Vertex &v = V[it->first];
        if (v.marker != marker)
          if ((v.distance = u.distance + E[it->second].distance) <= d)
            q.push_back(it->first);
      }
    }
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, q, a, b, c;
  cin >> n >> m >> q;
  long d;
  Graph g(n);
  while (m-- && cin >> a >> b >> d)
    g.E[g.connect(--a, --b)].distance = d;
  while (q-- && cin >> n >> a)
    switch (n) {
    case 1:
      cin >> b >> d;
      g.E[g.connect(--a, --b)].distance = d;
      break;
    case 2:
      cin >> b;
      g.disconnect(--a, --b);
      break;
    case 3:
      cin >> d >> c;
      g.color(--a, d, c);
      break;
    default:
      cout << g.V[--a].color << '\n';
    }
}