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
#include <iostream>
#include <list>
#include <queue>
using namespace std;

long long distances[100001];

class Path {
public:
	int target = 0;
	long long cost = 0;

	Path(int t = 0, long long c = 0) {
		this -> target = t;
		this -> cost = c;
	}
};

class Compare
{
public:
    bool operator() (int a, int b)
    {
    	return (distances[a] == -1) || distances[a] > distances[b];
    }
};

int main() {
	list<Path> p[100001];
	priority_queue<long long, std::deque<long long>, Compare> Q;
	long long z[100001];

	int n, q;
	cin >> n >> q;

	for(int i = 0; i < n; i++) {
		cin >> z[i+1];
	}

	for(int i = 0; i < n-1; i++) {
		int a, b;
		long long c;
		cin >> a >> b >> c;
		p[a].push_back(Path(b, c));
		p[b].push_back(Path(a, c));
	}

	int current = 1;

	for(int i = 0; i < q; i++) {
		//getting and updating changes
		int type;
		cin >> type;

		if(type == 1) {
			int v, d;
			cin >> v >> d;
			z[v] = d;
		}
		else {
			int a, b, d;
			cin >> a >> b >> d;
			for(list<Path>::iterator it = p[a].begin(); it != p[a].end(); ++it) {
				if((*it).target == b) {
					(*it).cost = d;
					break;
				}
			}
			for(list<Path>::iterator it = p[b].begin(); it != p[b].end(); ++it) {
				if((*it).target == a) {
					(*it).cost = d;
					break;
				}
			}
		}

		//dijkstra
		for(int j = 0; j < n; j++) {
			distances[j+1] = -1;
		}
		distances[current] = 0;

		for(int j = 0; j < n; j++) {
			Q.push(j+1);
		}
		while (!Q.empty())
		{
			int u = Q.top();
			Q.pop();
			for(list<Path>::iterator it = p[u].begin(); it != p[u].end(); ++it) {
				int v = (*it).target;
				if(distances[v] == -1 || distances[v] > distances[u] + (*it).cost) {
					distances[v] = distances[u] + (*it).cost;
					Q.push(v);
				}
			}
		}

		int best = -1;
		for(int j = 0; j < n; j++) {
			if(j+1 == current) continue;
			if(best == -1 || distances[j+1] - z[j+1] < distances[best] - z[best]) {
				best = j+1;
			}
		}
		current = best;
		cout << current;
		if(i < q-1) cout << " ";
	}

	cout << endl;

	return 0;
}