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
#include<cstdio>
#include <list>

using namespace std;
const int MAX=100001;

struct Edge{
	//krawedz z v->w
	int v, w;
	long long int c;
	Edge *rev;  // wska?nik na kraw?d? wsteczn?
	Edge(int v_in, int w_in, long long int c_in){
		v = v_in;
		w = w_in;
		c = c_in;
	}
};

long long int z[MAX];
int V[MAX];

list<Edge> E[MAX+1];


long long int dfs(int x){
	long long int sum = z[x];
	for (list<Edge>::iterator  it = E[x].begin(); it != E[x].end(); it++) {
   		long long int tmp = dfs(it->w) - it->c;
   		if(sum < tmp){
   			sum=tmp;
		}
	}
	return sum;
}

int main(){
	int n, q, v, a, b, x;
	scanf("%d %d", &n, &q);
	long long int c, d;
	long long int wynik=0;
	for(int i=0; i < n; ++i){
		scanf("%lld", &z[i]);
	}
	for(int i=0; i < n; ++i){
		scanf("%d %d %lld", &a, &b, &c);
				E[a].push_back(Edge(a,b,c));
				//E[a].back().rev = &E[b].back();
				E[b].push_back(Edge(b,a,c));
				//E[b].back().rev = &E[a].back();
				V[a]=0;
				V[b]=0;
	}
	for(int i=0; i < q; ++i){
		scanf("%d", x);
		if(x==1){
			scanf("%d %lld", &v, &d);
			z[v]=d;
			wynik+=dfs(1);
		}else{
			scanf("%d %d %lld", &a,&b,&d);
			for(int i=0; i < n; ++i){
				V[i]=0;
			}
			
		}
	}
	printf("%lld", wynik);
}