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
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>

using namespace std;

#define INF LLONG_MAX // max price
 
const int sz=100001; // max verticles
vector<pair<int,long long> > a[sz]; // adjacency list
long long income[sz]; // income in cities
long long dis[sz]; //shortest distance
bool vis[sz]={0};  // if visited

class prioritize {
    public: bool operator ()(pair<int, int>&p1 ,pair<int, int>&p2) {
        return p1.second>p2.second;
    }
};
 
void Dijkstra(int source, int n) //Algorithm for SSSP 
{
    for(int i=0;i<=n;i++) { //Set initial distances to Infinity
        dis[i] = INF;
        vis[i] = 0;
    }
    
    priority_queue<pair<int,int> ,vector<pair<int,int> >, prioritize> pq; //Priority queue to store vertex,weight pairs
    pq.push(make_pair(source,dis[source]=0)); //Pushing the source with distance from itself as 0
    while(!pq.empty())
    {
        pair<int, int> curr=pq.top(); //Current vertex. The shortest distance for this has been found
        pq.pop();
        int cv=curr.first,cw=curr.second; //'cw' the final shortest distance for this vertex
        if(vis[cv]) { //If the vertex is already visited, no point in exploring adjacent vertices
            continue;
        }
        vis[cv]=true; 
        for(int i=0;i<a[cv].size();i++) { //Iterating through all adjacent vertices
            if(!vis[a[cv][i].first] && a[cv][i].second+cw<dis[a[cv][i].first]) { //If this node is not visited and the current parent node distance+distance from there to this node is shorted than the initial distace set to this node, update it
                pq.push(make_pair(a[cv][i].first,(dis[a[cv][i].first]=a[cv][i].second+cw))); //Set the new distance and add to priority queue
             }
        }
    }
}

void printTime() {
    static int start = clock();
    static int i = 0;
    clock_t end = clock();
    if (i > 0) {
        double elapsed_secs = double(end - start) / CLOCKS_PER_SEC;
        start = end;
        cout << i << " Time: " << elapsed_secs << endl;
    }
    i++;
}

int main( ) {
    int n,q;
    scanf("%d %d", &n, &q);
    //cout << n << " " << q << endl;
    int m = n-1; // number of edges
    int x,y;
    long long w;
    //clock_t begin = clock();
    for (int i = 1; i <= n; i++) {
        cin>>w;
        income[i] = w;
    }
    for (int i = 0;i < m;i++) {
        cin>>x>>y>>w; // vertex start, vertex end, weight of edge
        // cout << "(" << x << ", " << y << ") -> " << w << endl;
        a[x].push_back(make_pair(y,w));
        a[y].push_back(make_pair(x,w));
    }
    int currentCity = 1; // where we currently are
    for(int i = 0; i < q; i++) {
        cin>>x;
        if (x == 1) {
           cin >> y >> w;
           income[y] = w;
        } else if (x == 2) {
           cin >> x >> y >> w;
           bool found = false;
           for (int j = 0; j < a[x].size(); j++) {
               if(a[x][j].first == y) {
                   a[x][j].second = w;
                   found = true;
                   break;
               }
           }
           if (!found) {
               a[x].push_back(make_pair(y,w));
           }
           found = false;
           for (int j = 0; j < a[y].size(); j++) {
               if(a[y][j].first == x) {
                   a[y][j].second = w;
                   found = true;
                   break;
               }
           }
           if (!found) {
               a[y].push_back(make_pair(x,w));
           }
        }
        Dijkstra(currentCity,n);
        int maxCity = -1;
        long long maxProfit = LLONG_MIN;
        for(int j=1;j<=n;j++)
        {
            //cout << j << ":" << income[j] << " " << dis[j] << endl;
            if (currentCity !=j && income[j]-dis[j] > maxProfit) {
                maxCity = j;
                maxProfit = income[j]-dis[j];
                //cout << "New max: [" << maxCity <<  " -> " << maxProfit << "]" << endl;
            }
        }
        currentCity = maxCity;
        if ( i > 0 ) {
            cout << " ";
        }
        cout << maxCity;
        //cout << " ###" << endl;
    }
    //cout << endl;
    //clock_t end = clock();
    //double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    //cout << endl << "Time: " << elapsed_secs << endl;
    return 0;
}