#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



#ifndef aa
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
#define done(x) {cout << x << endl;return;}
#define mini(x,y) x=min(x,y)
#define maxi(x,y) x=max(x,y)
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//const int mod = 998244353;
const int mod = 1e9 + 7;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpii;
typedef map<int, int> mii;
typedef set<int> si;
typedef set<pair<int,int>> spii;
typedef queue<int> qi;
uniform_int_distribution<int> rng(1,1e9);

//DEBUG FUNCTIONS START
#define cerr cout
void __print(int x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = "; _print(x)
#else
#define deb(x...)
#endif
// DEBUG FUNCTIONS END




const int N = 2e5+5;

int c[N], p[N], sz[N];
map<int, ordered_set> mp;

int find(int x){
	if(x==p[x])
		return x;
	return p[x] = find(p[x]);
}

void join(int x, int y){
	x = find(x), y = find(y);
	if(x==y)
		return;
	if(sz[x]>sz[y]){
		swap(x, y);
	}
	sz[y] += sz[x];
	p[x] = y;
	trav(t, mp[x]){
		mp[y].insert(t);
	}
	
}

void solve(){
	
	ordered_set d;
	
	int n, q;
	cin>>n>>q;
	fr(i,1,n){
		cin>>c[i];
		mp[i].insert({c[i], i});
		p[i] = i;
		sz[i] = 1;
	}
	while(q--){
		int x, y, z;
		cin>>x>>y>>z;
		
		if(x==1){
			join(y, z);
		}else{
			y = find(y);
			auto it1 = mp[y].lb(pii(z,0));
			auto it2 = mp[y].lb(pii(z, infl));
			
			int ans = (it2 == mp[y].end() ? sz(mp[y]) : mp[y].order_of_key(*it2)) - (it1 == mp[y].end() ? sz(mp[y]) : mp[y].order_of_key(*it1));
			cout<<ans<<endl;
		}
		
	}
	
		
	
}



signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    cout << fixed << setprecision(15);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
#ifdef aa
    cout << endl << endl << endl << endl << "Time elapsed: " << (double)(clock() - clk) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

int powm(int a, int b){
    int res = 1;
    while (b) {
        if (b & 1)
            res = (res*a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
int divide(int a, int b) {
    return (a % mod) * powm(b % mod, mod - 2) % mod;
}
 
int norm(int a) {
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return a;
}
#include <bits/stdc++.h>
using namespace std;
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long LINF = 1LL << 60;

struct Edge {
    int to;
    long long w;
    Edge(int arg_to, long long arg_w) : to(arg_to), w(arg_w) {}
};

using Graph = vector<vector<Edge>>;

int N, M;

long long dijkstra(Graph G, int s, int g) {
    int min_v;
    vector<long long> dist(N, LINF);
    priority_queue<pair<long long, int>> pq;

    dist[s] = 0;
    pq.emplace(-dist[s], s);

    while (!pq.empty()) {
        min_v = pq.top().second;
        pq.pop();

        for (auto e : G[min_v]) {
            if (chmin(dist[e.to], dist[min_v] + e.w)) {
                pq.emplace(-dist[e.to], e.to);
            }
        }
    }
    return dist[g];
}

int main() {
    cin >> N >> M;
    Graph G(N);
    vector<vector<int>> to(N);
    int A, B, C;
    rep(i, M) {
        cin >> A >> B >> C; A--; B--;
        G[A].push_back(Edge(B, C));
        to[B].push_back(A);
    }
    long long res;
    rep(i, N) {
        res = LINF;
        for (Edge e : G[i]) if (e.to == i) chmin(res, e.w);
        for (int j : to[i]) {
            if (i == j) continue;
            chmin(res, dijkstra(G, i, j) + dijkstra(G, j, i));
        }
        if (res != LINF) cout << res << endl;
        else cout << "-1" << endl;
    }
}

