#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int main() {
  int n,m;
  while(cin>>n>>m, n+m) {
    int p[n];
    REP(i,n) 
      cin >> p[i];
    vector<int> v(n*n);
    REP(i,n)
      REP(j,n)
      v[i*n + j] = p[i] + p[j];
    v.push_back(0);
    REP(i,n)
      v.push_back(p[i]);
    sort(ALL(v));
    // FOR(it, v)
    //   cout << *it << " ";
    // cout << endl;
    int res = 0; 
    REP(i,v.size()) {
      vector<int>::iterator it = upper_bound(ALL(v), m-v[i]);
      int tmp;
      if (it == v.begin()) {
        break;
      } else {
        it--;
        tmp = v[i] + *it;
      }
      res = max(res, tmp);
    }
    cout << res << endl;
  }
}
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	while(true){
		int n, k, x, a, b, fee[101][101];
		cin >> n >> k;
		
		if(n == 0 && k == 0){
			break;
		}
		
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				fee[i][j] = 1000000000;
			}
		}
		
		for(int i = 0; i < k; i++){
			cin >> x >> a >> b;
			
			if(x){
				cin >> fee[a][b];
				fee[b][a] = fee[a][b] = min(fee[a][b], fee[b][a]);
				
				for(int j = 1; j <= n; j++){
					for(int l = 1; l <= n; l++){
						fee[j][l] = min(fee[j][l], fee[j][a] + fee[a][l]);
						fee[l][j] = fee[j][l] = min(fee[j][l], fee[j][b] + fee[b][l]);
					}
				}
			} else{
				if(fee[a][b] != 1000000000){
					cout << fee[a][b] << endl;
				} else{
					cout << -1 << endl;
				}
			}
		}
	}
	return 0;
}