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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) (int)(x).size()
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define REP(x, n) for(int x = 0; x < (n); x++)
#define FOR(x, b, e) for(int x = (b); x <= (e); x++)
#define FORD(x, b, e) for(int x = (b); x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__)

typedef long long int LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MXN = 1000000;
const int C = 262144;
const LL INF = 1LL << 61;
const int MOD = 1000000007;

int n, m, q;

vector<PII> G[MXN];
LL dist[MXN];
map<PII, int> edges;
int kolor[MXN];

void update(int v, int d, int k) {
	FOR(i, 1, n) {
		G[i].clear();
		dist[i] = INF;
	}
	FOREACH(it, edges) {
		PII p1 = it -> F;
		G[p1.F].PB(MP(p1.S, it -> S));
		G[p1.S].PB(MP(p1.F, it -> S));
	}

	queue<int> Q;
	Q.push(v);
	dist[v] = 0;

	while(!Q.empty()) {
		int w = Q.front();
		Q.pop();
		if(dist[w] > d)
			continue;
		kolor[w] = k;

		FOREACH(it, G[w]) {
			if(dist[it -> F] == INF) {
				dist[it -> F] = dist[w] + it -> S;
				Q.push(it -> F);
			}
		}
	}
}

void test() {
	scanf("%d %d %d", &n, &m, &q);
	FOR(i, 1, m) {
		int a, b, d;
		scanf("%d %d %d", &a, &b, &d);
		if(a > b)
			swap(a, b);
		edges[MP(a, b)] = d;
	}

	FOR(i, 1, q) {
		int typ;
		scanf("%d", &typ);
		if(typ == 1) {
			int a, b, d;
			scanf("%d %d %d", &a, &b, &d);
			if(a > b)
				swap(a, b);
			edges[MP(a, b)] = d;
		}
		else if(typ == 2) {
			int a, b;
			scanf("%d %d", &a, &b);
			if(a > b)
				swap(a, b);
			edges.erase(MP(a, b));
		}
		else if(typ == 3) {
			int v, d, k;
			scanf("%d %d %d", &v, &d, &k);
			update(v, d, k);
		}
		else {
			int a;
			scanf("%d", &a);
			printf("%d\n", kolor[a]);
		}
	}
}

int main() {
	int te = 1;
//	scanf("%d", &te);
	while(te--)
		test();
	return 0;
}