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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <cstdio>
#include <vector>
#include <list>
#include <climits>
using namespace std;

void change_verticles(int a2, int b2, long long int d2);
void BFS(int root, int n);
void clear_results_table(int n);
int find_max_BFS_result(int n);


class Node {
public:
    int number_connected_node;
    long long int road_payment;

    Node(int number, long long int payment) {
        number_connected_node = number;
        road_payment = payment;
    }
};

vector<vector<Node>> cities(100003);
long long int earn[100003];
long long int BFS_results[100003];
bool visited[100003];



int main() {
    int n,q;
    int a,b;
    long long int c;
    int option;
    int v;
    long long int d; 
    int a2,b2;
    long long int d2;
    int start = 1;

    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &earn[i]);
    }
    
    for(int i = 1; i < n; i++) {
        scanf("%d%d%lld", &a, &b, &c);
        cities[a].push_back(Node(b,c));
        cities[b].push_back(Node(a,c));
    }

    
    for(int i = 0; i < q; i++) {
        scanf("%d", &option);
        if(option == 1) {
            scanf("%d%lld", &v, &d);
            earn[v] = d;
        }
        if(option == 2) {
            scanf("%d%d%lld", &a2, &b2, &d2);
            change_verticles(a2, b2, d2);
        }     
        
        BFS(start,n);
        start = find_max_BFS_result(n);
        printf("%d ", start);
        clear_results_table(n);    
    }
    printf("\n");
    return 0;
}


void change_verticles(int a2, int b2, long long int d2) {
    for(int i = 0; i < cities[a2].size(); i++) {
        if(cities[a2][i].number_connected_node == b2) {
            cities[a2][i].road_payment = d2;
        }
    }

    for(int i = 0; i < cities[b2].size(); i++) {
        if(cities[b2][i].number_connected_node == a2) {
            cities[b2][i].road_payment = d2;
        }
    }
}

//copied and modified from http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
void BFS(int root, int n) {
    for(int i = 1; i <= n; i++)
        visited[i] = false;

    list<int> queue;
    list<long long int> queue_dist;
    queue_dist.push_back(0L);
    visited[root] = true;
    queue.push_back(root);
    int s;
    long long int dist;

    while(!queue.empty()) {
        s = queue.front();
        queue.pop_front();
        dist = queue_dist.front();
        queue_dist.pop_front();
        if(root == s) {
            BFS_results[root] = LLONG_MIN;
        }
        else {
            BFS_results[s] = earn[s] - dist;
        }
        
        int k;
        long long int d;
        for (int i = 0; i < cities[s].size(); ++i) {
            k = cities[s][i].number_connected_node;
            d = cities[s][i].road_payment + dist;
            if (!visited[k]) {
                visited[k] = true;
                queue.push_back(k);
                queue_dist.push_back(d);
            }        
        }
    }
}


void clear_results_table(int n) {
    for(int i = 1; i <= n; i++) {
        BFS_results[i] = 0;
    }
}

int find_max_BFS_result(int n) {
    long long int result = LLONG_MIN;
    int result_index = -1;
    for(int i = 1; i <= n; ++i) {
        if(BFS_results[i] > result) {
            result = BFS_results[i];
            result_index = i;
        }
    }
    return result_index;
}