#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mkp make_pair
int dis[2002];
int n,m;
vector<pii>g[2002];
void dij(int s){
	for(int i=0;i<2002;i++)dis[i]=1e9;
	priority_queue<pii,vector<pii>,greater<pii> >pq;
	for(auto x:g[s])
		if(dis[x.fi]>x.se)dis[x.fi]=x.se,pq.push(mkp(x.se,x.fi));
	while(!pq.empty()){
		pii u=pq.top();pq.pop();
		if(dis[u.se]<u.fi)continue; 
		for(auto x:g[u.se])
			if(dis[x.fi]>u.fi+x.se)
				dis[x.fi]=u.fi+x.se,pq.push(mkp(x.se+u.fi,x.fi));
	}
	cout<<(dis[s]==1e9?-1:dis[s])<<"\n";
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v,w;cin>>u>>v>>w;
		g[u].push_back(mkp(v,w));
	}
	for(int i=1;i<=n;i++)dij(i);
}
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
#include <cstdint>
#include <string>
#include <sstream>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using P = pair<int,int>;
const int INF=1001001001;
const int mod =1e9+7;

struct Unionfind{
   vector<int>d;
   vector<map<int,int>>mp;
   Unionfind(int n):d(n,-1),mp(n){}
   int root(int x){
     if(d[x]<0){return x;}
     return d[x]=root(d[x]);
   }
   bool unite(int x,int y){
     x=root(x);y=root(y);
     if(x==y){return false;}
     if(d[x]>d[y]){swap(x,y);}
     for(auto p:mp[y]){
       mp[x][p.first]+=p.second;
     }
     mp[y]=map<int,int>();
     d[x]+=d[y];
     d[y]=x;
     return true;
   }
   bool same(int x,int y){return root(x)==root(y);}
   int size(int x){return -d[root(x)];}
};

int main() {
  int N,Q;cin>>N>>Q;
  Unionfind uf(N);
  rep(i,N){
    int c;cin>>c;uf.mp[i][c]=1;
  }
  rep(i,Q){
    int q;cin>>q;
    if(q==1){
      int a,b;cin>>a>>b;a--;b--;
      uf.unite(a,b);
    }
    else{
      int x,y;cin>>x>>y;x--;
      int r=uf.root(x);
      cout<<uf.mp[r][y]<<endl;
    }
  }
  return 0;
}