#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a) for(int i = 0; i < (int) a; i++)
#define PB push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int grid[2007][2007];

int n;
vector<pair<int,int>> graph[2007];
int dist[2007];

void dijsktra(int s){
	for(int i = 0; i < n; i++) dist[i] = INT_MAX;
	priority_queue<pair<int,int>, 
				   vector<pair<int,int>>, 
				   ::greater<pair<int,int>> > q;
	q.push({0, s});
	bitset<2007> vis(0);
	while(!q.empty()){
		int now = q.top().second; q.pop();
		if(vis[now]) continue;

		vis[now] = 1;

		for(auto v : graph[now]){
			if(now == s){
				dist[v.second] = v.first;
				q.push({dist[v.second], v.second});
			}else if(dist[v.second] > dist[now] + v.first){
				dist[v.second] = dist[now] + v.first;
				q.push({dist[v.second], v.second});
			}
		}

	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);

	int m; cin >> n >> m;
	FOR(i, n) FOR(j, n) grid[i][j] = 1e9;

	FOR(i, m){
		int a, b, c; cin >> a >> b >> c;
		a--; b--;
		grid[a][b] = min(grid[a][b], c);
	}

	FOR(i, n){
		FOR(j, n){
			if(grid[i][j] != 1e9){
				graph[i].PB({grid[i][j], j});
			}
		}
	}
	

	FOR(i, n){
		dijsktra(i);
		if(dist[i] == INT_MAX) cout << "-1\n";
		else cout << dist[i] << '\n';
	}


	return 0;
}
#include <bits/stdc++.h>

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;
using llpair = pair<llong, lpair>;

#define ALL(x) x.begin(), x.end()

constexpr llong mod = 1e9+7;
constexpr llong inf = mod * mod;

struct union_find {
  std::vector<int> par;
  vector<unordered_map<int, int>> sum;

  union_find() {}
  union_find(int n) :
    par(n+1, -1)
  {}

  int root(int x) {
    if(par[x] < 0) return x;
    return par[x] = root(par[x]);
  }
  int size(int x) {
    return -par[root(x)];
  }
  bool same(int a, int b) {
    return root(a) == root(b);
  }
  bool marge(int a, int b) {
    a = root(a), b = root(b);
    if(a == b) return false;
    if(par[a] > par[b]) std::swap(a, b);
    par[a] += par[b];
    par[b] = a;
    for (auto it: sum[b]) {
      sum[a][it.first] += it.second;
    }
    return true;
  }
  int query(int x, int y) {
    return sum[root(x)][y];
  }
};


int main() {
  llong N, Q;
  vector<llong> C;
  vector<llpair> query;

  cin >> N >> Q;
  C.resize(N);
  for (auto &in: C) {
    cin >> in;
    in--;
  }
  query.resize(Q);
  for (auto &in: query) {
    cin >> in.first >> in.second.first >> in.second.second;
    in.second.first--;
    in.second.second--;
  }

  union_find uf(N);
  uf.sum.resize(N);
  for (int i = 0; i < N; i++) {
    uf.sum[i][C[i]] = 1;
  }
  for (auto q: query) {
    if (q.first == 1) {
      llong a = q.second.first;
      llong b = q.second.second;
      uf.marge(a, b);
    }
    else {
      llong x = q.second.first;
      llong y = q.second.second;
      cout << uf.query(x, y) << endl;
    }
  }

  return 0;
}