#define _USE_MATH_DEFINES
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include <cassert>
#include <numeric>
#include <unordered_map>
#include <queue>
#include <math.h>
#include <climits>
#include <set>
#include <map>
using namespace std;

using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
//template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;

#define FOR(i, a, b) for(ll i=(a); i<(b);i++)
#define REP(i, n) for(ll i=0; i<(n);i++)
#define ROF(i, a, b) for(ll i=(b-1); i>=(a);i--)
#define PER(i, n) for(ll i=n-1; i>=0;i--)
#define REPREP(i,j,a,b) for(ll i=0;i<a;i++)for(ll j=0;j<b;j++)
#define VV(type) vector< vector<type> >
#define VV2(type,n,m,val) vector< vector<type> > val;val.resize(n);for(ll i;i<n;i++)val[i].resize(m)
#define vec(type) vector<type>
#define VEC(type,n,val) vector<type> val;val.resize(n)
#define VL vector<ll>
#define VVL vector< vector<ll> >
#define SZ size()
#define all(i) begin(i),end(i)
#define SORT(i) sort(all(i))
#define BITI(i) (1<<i)
#define BITSET(x,i) x | (1<<i)
#define BITCUT(x,i) x & ~(1<<i)
#define EXISTBIT(x,i) ((x>>i) & 1 != 0)
#define ALLBIT(n) (1<<n-1)

class UndirectedGraph {
public:
  struct edge { ll to,cost; };  // 行先,容量,逆容量,コスト

  UndirectedGraph(ll n) {
    edges.resize(n);
  }
  void addEdge(ll from, ll to, ll cost) {
    edge eF = { to,cost };
    edges[from].push_back(eF);
    edge eT = { from,cost };
    edges[to].push_back(eT);
  }

  void FindConnect(ll v, vector<bool>& out) {
    out.assign(edges.size(), false);
    vector<ll> stack;
    stack.push_back(v);
    out[v] = true;
    while (!stack.empty()) {
      v = stack.back(); stack.pop_back();
      for (int i = 0; i < edges[v].size(); i++) {
        ll t = edges[v][i].to;
        if (!out[t]) {
          out[t] = true;
          stack.push_back(t);
        }
      }
    }
  }
  vector<vector<edge>> edges;
};

int main() {
  ll n, m;
  cin >> n >> m;
  VL a(m), b(m), c(m);
  UndirectedGraph g(n);

  REP(i, m) {
    char cc;
    cin >> a[i] >> b[i] >> cc;
    a[i]--; b[i]--;
    c[i] = cc - 'a';
    g.addEdge(a[i], b[i], c[i]);
  }
  
  queue<tuple<ll, ll, ll>> que;
  vector<vector<bool>> used(n);
  REP(i, n) {
    used[i].assign(n, false);
  }
  que.push({ 0,0,n - 1 });
  used[0][n - 1] = true;
  used[n - 1][0] = true;

  ll find = -1;
  while (!que.empty()) {
    auto [dist, l, r] = que.front();
    que.pop();
    if (find != -1 && find < dist) {
      cout << find * 2 + 1;
      return 0;
    }
    if (l == r) {
      cout << dist * 2;
      return 0;
    }
    REP(i, g.edges[l].size()) {
      REP(j, g.edges[r].size()) {
        if (g.edges[l][i].cost == g.edges[r][j].cost) {
          if (g.edges[l][i].to == r && g.edges[r][j].to == l) {
            find = dist;
            continue;
          }
          if (used[g.edges[l][i].to][g.edges[r][j].to])
            continue;
          que.push({ dist + 1,g.edges[l][i].to ,g.edges[r][j].to });
          used[g.edges[l][i].to][g.edges[r][j].to] = true;
          used[g.edges[r][j].to][g.edges[l][i].to] = true;
        }
      }
    }
  }
  if (find != -1) {
    cout << find * 2 + 1;
    return 0;
  }
  cout << -1;
}

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


#define pb push_back
#define fi first
#define se second
#define ll long long
#define tp top()
#define fr front()
#define vi vector<int>
#define sz size()
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define mem(a,  b) memset(a,  (b),  sizeof(a))
#define clr(a) memset(a,  0,  sizeof(a))
#define sqr(x) ( (x) * (x) )
#define all(v) v.begin(),  v.end()

typedef pair<int, int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;



void base(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

void solve(){
//	rep(i,1,40){
//		cout<<i<<" -> "<<8*i<<"\n";
//	}
	string s; cin>>s;
	char ch[20]={0};
	rep(i,0,s.sz) ch[s[i]-'0']++;
	bool found = 0;
	rep(i,0,10) {
		if (ch[i]==0) continue;
		ch[i]--;
		if (s.sz == 1) {
			if (i % 8 == 0) found = 1;
			continue;
		}
		rep(j,0,10){
			if (ch[j]==0) continue;
			ch[j]--;
			int res = i*10 + j;	
			bool hasodd=0, haseven=0;
			
			rep(k,0,10){
				if (k&1) {
					if (ch[k]>0) hasodd=1;
				} else {
					if (ch[k]>0) haseven=1;
				}
			}
			if (s.sz == 2) haseven = 1;
			if (haseven && (res % 8 == 0)) found = 1;
			if (hasodd && ((res+4) % 8 == 0)) found = 1;			
			ch[j]++;
		}
		ch[i]++;
	}

	if (found) cout<<"Yes\n";
	else cout<<"No\n";
}

int main()
{
	base();
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}




