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
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<climits>

int n,q;
long long * profit;
std::vector<std::map<int, long long> > graph;
bool * visited;
long long * cost;

void print_graph() {
  for (int i = 0; i < n; i++) {
    printf("%d:\n", i + 1);
    for (std::map<int, long long>::iterator it = graph[i].begin(); it != graph[i].end(); it++) {
      printf("(%d, %lld) ", it -> first + 1, it -> second);
    }
    printf("\n");
  }
}

void input() {
  scanf("%d %d", &n, &q);
  profit = new long long[n];
  visited = new bool[n];
  cost = new long long[n];
  for (int i = 0; i < n; i++) {
    scanf("%lld", profit + i);
    graph.push_back(std::map<int, long long>());
  }
  int v, w;
  long long z;
  for (int i = 0; i < n - 1; i++) {
    scanf("%d %d %lld", &v, &w, &z);
    graph[v - 1][w - 1] = z;
    graph[w - 1][v - 1] = z;
  }
}

long long min(long long a, long long b) {
  return a < b ? a : b;
}

int progres(int city) {
  //printf("CITY=%d\n", city);
  for (int i = 0; i < n; i++) {
    visited[i] = false;
    cost[i] = LLONG_MAX;
  }

  long long best_profit = LLONG_MIN;
  int best = city;
  cost[city] = 0;
  std::queue<int> Q;
  Q.push(city);

  while(!Q.empty()) {
    int v = Q.front();
    //printf("v=%d\n", v);
    Q.pop();
    if (!visited[v]) {
      visited[v] = true;
      for (std::map<int, long long>::iterator it = graph[v].begin(); it != graph[v].end(); it++) {
        int w = it -> first;
        cost[w] = min(cost[w], cost[v] + it -> second);
        if (!visited[w]) {
          Q.push(w);
        }
      }
    }
  }/*
  printf("CITY=%d\n", city);
  print_graph();
  for (int i = 0; i < n; i++) {
    printf("%3lld ", cost[i]);
  }
  printf("\n");
  for (int i = 0; i < n; i++) {
    printf("%3lld ", profit[i]);
  }
  printf("\n");*/

  for (int i = 0; i < n; i++) {
    if (i != city) {
      if (best_profit < profit[i] - cost[i]) {
        best_profit = profit[i] - cost[i];
        best = i;
      }
    }
  }

  return best;
}

void solve() {
  int t, a, b;
  long long c;
  int city = 0;
  for (int i = 0; i < q; i++) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d %lld", &a, &c);
      profit[a - 1] = c;
    } else {
      scanf("%d %d %lld", &a, &b, &c);
      graph[a - 1][b - 1] = c;
      graph[b - 1][a - 1] = c;
    }
    city = progres(city);
    printf("%d ", city + 1);
  }
  printf("\n");
}

int main(int argc, char ** argv) {
  input();
  solve();
  return 0;
}