#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 105;
const int MAX_M = 1e4 + 5;

#define u first
#define v second

pair<int, int> edges [MAX_M];
int dir [MAX_M];

vector<int> adj [MAX_N]; // idx of the edge
int arr [MAX_N];
int vis [MAX_N];

void direct (int u) {
  vis[u] = 1;
  for (int e : adj[u]) {
    if (dir[e] == 0) {
      if (u == edges[e].u) {
        dir[e] = 1;
      } else {
        dir[e] = -1;
      }

      int oth = edges[e].u ^ edges[e].v ^ u;
      if (!vis[oth]) {
        direct(oth);
      }
    }
  }
}

int main () {
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    cin >> edges[i].u >> edges[i].v;
    
    adj[edges[i].u].push_back(i);
    adj[edges[i].v].push_back(i);
  }

  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
  }

  for (int i = 0; i < m; i++) {
    if (arr[edges[i].u] > arr[edges[i].v]) {
      dir[i] = 1;
    } else if (arr[edges[i].u] < arr[edges[i].v]) {
      dir[i] = -1;
    }
  }

  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      vis[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
      if (!vis[i] && arr[i] == k) {
        direct(i);
      }
    }
  }

  for (int i = 0; i < m; i++) {
    if (dir[i] == 1) {
      cout << "->" << '\n';
    } else {
      cout << "<-" << '\n';
    }
  }
}

#include <bits/stdc++.h>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using ld = long double;
using vld = vector<ld>;
using vb = vector<bool>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

template <class T> bool chmin(T& a, T b) {
    if(a > b) { a = b; return true; }
    else return false;
}

template <class T> bool chmax(T& a, T b) {
    if(a < b) { a = b; return true; }
    else return false;
}

template <class T> ostream& operator<<(ostream& s, const vector<T>& a) {
    for(auto i : a) s << i << ' ';
    return s;
}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 62;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll n, m;
    cin >> n >> m;
    using P = pair<ll, char>;
    vector<vector<P>> g(n);
    while(m--) {
        ll a, b;
        char c;
        cin >> a >> b >> c;
        --a, --b;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    vvll dist(n, vll(n, INFL));
    dist[0][n-1] = 0;
    queue<pll> que;
    que.emplace(0, n-1); // v0, v1
    ll ans = INFL;
    while(!que.empty()) {
        ll v0 = que.front().first;
        ll v1 = que.front().second;
        que.pop();
        ll d = dist[v0][v1];
        for(auto [nv0, c0] : g[v0]) {
            if(nv0 == v1) {
                chmin(ans, 2*d + 1);
                continue;
            }
            for(auto [nv1, c1] : g[v1]) {
                if(c0 != c1) continue;
                if(nv0 == nv1) {
                    chmin(ans, 2*(d+1));
                    continue;
                }
                if(chmin(dist[nv0][nv1], d+1)) {
                    que.emplace(nv0, nv1);
                }
            }
        }
    }
    if(ans == INFL) cout << -1 << endl;
    else cout << ans << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}