/*  -*- coding: utf-8 -*-
 *
 * f.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 200000;

/* typedef */

typedef map<int,int> mii;

struct UFT {
  int links[MAX_N], ranks[MAX_N], sizes[MAX_N];
  UFT() {}

  void init(int n) {
    for (int i = 0; i < n; i++) links[i] = i, ranks[i] = sizes[i] = 1;
  }

  int root(int i) {
    int i0 = i;
    while (links[i0] != i0) i0 = links[i0];
    return (links[i] = i0);
  }

  int rank(int i) { return ranks[root(i)]; }
  int size(int i) { return sizes[root(i)]; }
  bool same(int i, int j) { return root(i) == root(j); }

  int merge(int i0, int i1) {
    int r0 = root(i0), r1 = root(i1), mr;
    if (r0 == r1) return r0;
    if (ranks[r0] == ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      ranks[r0]++;
      mr = r0;
    }
    else if (ranks[r0] > ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      mr = r0;
    }
    else {
      links[r0] = r1;
      sizes[r1] += sizes[r0];
      mr = r1;
    }
    return mr;
  }
};

/* global variables */

mii cvs[MAX_N];
UFT uft;

/* subroutines */

/* main */

int main() {
  int n, qn;
  scanf("%d%d", &n, &qn);

  for (int i = 0; i < n; i++) {
    int ci;
    scanf("%d", &ci);
    ci--;
    cvs[i][ci] = 1;
  }

  uft.init(n);

  while (qn--) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    x--, y--;

    if (op == 1) {
      if (! uft.same(x, y)) {
	int rx = uft.root(x), ry = uft.root(y);
	int u = uft.merge(rx, ry), v = (u == rx) ? ry : rx;

	mii &cvu = cvs[u], &cvv = cvs[v];
	if (cvu.size() < cvv.size()) swap(cvu, cvv);

	for (mii::iterator mit = cvv.begin(); mit != cvv.end(); mit++)
	  cvu[mit->first] += mit->second;
      }
    }
    else {
      mii &cvr = cvs[uft.root(x)];

      mii::iterator mit = cvr.find(y);
      if (mit == cvr.end() || mit->first != y) puts("0");
      else printf("%d\n", mit->second);
    }
  }
  return 0;
}

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

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());//uniform_int_distribution<int> (l, r)

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 1e5 + 123;
const int M = 1e6 + 123;
const double pi = 3.14159265359;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

struct edge{
    int u, v, c, d, opt;
}e[N];

vector<int> g[N];

ll dis[N];

void solve(){
    int n, m;
    cin >> n >> m;
    for (int i = 1, u, v, c, d; i <= m; i++){
        cin >> u >> v >> c >> d;
        g[u].pb(i);
        g[v].pb(i);
        int l = 0;
        if (d){
            l = sqrt(d)-1;
            while (l+(d/(l+1)) > l+1+(d/(l+2))){
                l++;
            }
        }
        e[i] = {u, v, c, d, l};

        //cout << l << ndl;
    }
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> q;
    q.push({0, 1});

    while (!q.empty()){
        ll d;
        int v;
        tie(d, v) = q.top();
        q.pop();
        if (dis[v] != d) continue;
        for (int i : g[v]){
            
            ll x = max(e[i].opt+0ll, d);
            
            int u = e[i].v+e[i].u - v;

            if (dis[u] > x + e[i].c + e[i].d/(x+1)){
                dis[u] = x + e[i].c + e[i].d/(x+1);
                q.push({dis[u], u});
            }
        }
    }
    if (dis[n] > INF){
        cout << -1;
    }
    else{
        cout << dis[n];
    }
}

int main(){
    #ifdef me
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;  
    //cin >> t;
    for (int i = 1; i <= t; i++){
        //cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef KAZAKH
      //  cout << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl;
    #endif
    return 0;
}