1

#include <bits/stdc++.h>
#define int64_t long long
using namespace std;

const int N = 1e5 + 5;
const int oo = 1e9 + 7;

typedef pair<int64_t, int> ii;

int n, q;
int a[N];

namespace Sub1 {
int64_t d[N];

void Dijkstra(int s, int f) {
   priority_queue<ii, vector<ii>, greater<ii>> pq;
   fill(d + 1, d + n + 1, oo);
   d[s] = 0;
   pq.push({0, s});

   while(!pq.empty()) {
      int u = pq.top().second;
      int64_t du = pq.top().first;
      pq.pop();

      if(u == f) return;
      if(du != d[u]) continue;

      for(int i = 1; i <= n; ++i) {
         int v = i;
         int64_t uv = a[u] * a[v];

         if(d[v] > d[u] + uv) {
            d[v] = d[u] + uv;
            pq.push({d[v], v});
         }
      }
   }
}

void solve() {
   for(int i = 1; i <= q; ++i) {
      int k, u, v;
      cin >> k >> u >> v;
      if(k == 1) a[u] = v;
      else {
         Dijkstra(u, v);
         cout << d[v] << '\n';
      }
   }
}
}//namespace Sub1

namespace Sub3 {
int d[105][105];

void minimize(int &a, int b) {
    if(a > b) a = b;
}

void Floyd() {
   for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++)
        d[i][j] = d[j][i] = a[i] * a[j];
   for(int i = 1; i <= n; i++)
      d[i][i] = 0;

   for(int k = 1; k <= n; k++)
      for(int i = 1; i <= n; i++)
         for(int j = 1; j <= n; j++)
               minimize(d[i][j], d[i][k] + d[k][j]);
}

void solve() {
   Floyd();
   for(int i = 1; i <= q; ++i) {
      int k, u, v;
      cin >> k >> u >> v;
      if(k == 1) {
         a[u] = v;
         Floyd();
      }
      else cout << d[u][v] << '\n';
   }
}
}//namespace Sub3

namespace Sub4 {
int minn = oo;

void solve() {
   for(int i = 1; i <= n; i++)
      minn = min(minn, a[i]);

   for(int i = 1; i <= q; ++i) {
      int k, u, v;
      cin >> k >> u >> v;
      if(k == 1) a[u] = v;
      else cout << min(a[u] * a[v], a[u]*minn + a[v]*minn) << '\n';
   }
}
}//namespace Sub4

int main() {
#ifdef LOCAL
   freopen("in.txt", "r", stdin);
#else
   freopen("MULTIGRAPH.inp", "r", stdin);
   freopen("MULTIGRAPH.out", "w", stdout);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);

   cin >> n >> q;
   for(int i = 1; i <= n; ++i)
      cin >> a[i];

   if(n <= 500 && q <= 500)
      Sub1::solve();
   else if(n <= 100)
      Sub3::solve();
   else
      Sub4::solve();

   return 0;
}