#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T1, class T2> inline bool chmax(T1 &a, const T2 &b) {if (a<b) { a=b; return 1;} return 0;}
template<class T1, class T2> inline bool chmin(T1 &a, const T2 &b) {if (b<a) { a=b; return 1;} return 0;}
struct init{init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(15);}}init_;

#ifdef DEBUG
template <class T> void verr(const set<T> &st) { repa(a, st) cerr << a << " "; cerr << endl; }
template <class S, class T> void verr(const map<S, T> &mp) { repa(a, mp) cerr << "{" << a.first << ", " << a.second << "} "; cerr << endl; }
template <class S, class T, class N> void verr(const vector<pair<S,T>>& a, const N& n) { rep(i, n) cerr << "{" << a[i].first << ", " << a[i].second << "} "; cerr << endl; }
template <class T, class N> void verr(const vector<T>& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << endl; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << endl; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    ll K, N, M;
    cin >> K >> N >> M;
    vl A(K);
    rep(i, K) cin >> A[i];

    ll ng = -1, ok = MOD * MOD;
    vl ansB;
    while(ok - ng > 1){
        ll mid = (ok + ng) / 2;

        ll dcnt = 0, ucnt = 0;
        rep(i, K){
            dcnt += max(0ll, (M * A[i] - mid + N - 1) / N);
            ucnt += (M * A[i] + mid) / N;
        }

        if(!(dcnt <= M and M <= ucnt)) {
            ng = mid;
            continue;
        }
        ok = mid;
        ll rest = M;
        vl B(K);
        rep(i, K) {
            B[i] = max(0ll, (M * A[i] - mid + N - 1) / N);
            rest -= B[i];
        }
        rep(i, K){
            ll d = (M * A[i] + mid) / N - B[i];
            chmin(d, rest);
            B[i] += d, rest -= d;
        }

        ansB = B;
    }

    repa(b, ansB) cout << b << " ";
    cout << endl;
    // err(ok);
}
#include <bits/stdc++.h>
using namespace std;

#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define prinv(v) cout << #v << " = "; for(auto it : v) cout << it << ", "; cout << endl
#define all(v) (v).begin(),(v).end()

typedef long long ll;

#define rmin(a,b) a = min<ll>(a,b)
#define rmax(a,b) a = max<ll>(a,b)

#define fi first
#define se second

const int N =1010;
vector<int> g[26][N];
int vis[N][N], nb[N][N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	fr(i,m){
		int a, b; char c; cin >> a >> b >> c;
		a--,b--;
		int ic=  c-'a';
		g[ic][a].push_back(b);
		g[ic][b].push_back(a);
		nb[a][b] = 1;
		nb[b][a] = 1;
	}
	fr(i,n) nb[i][i] = 1;
	
	int INF = INT_MAX/2;
	int ans = INF;
	queue<tuple<int,int,int>> q;
	q.emplace(0,0,n-1);
	vis[0][n-1] = 1;
	while(!q.empty()){
		int dac, a, b; tie(dac,a,b) = q.front(); q.pop();
		if(nb[a][b]){
			if(a==b) rmin(ans,dac);
			else rmin(ans,dac+1);
		}
		if(ans+2<dac) break;
		fr(ic,26){
			for(auto ann : g[ic][a]) for(auto bnn : g[ic][b]){
				int an = ann, bn = bnn;
				if(an>bn) swap(an,bn);
				if(vis[an][bn]) continue;
				q.emplace(dac+2,an,bn);
				vis[an][bn] = 1;
			}
		}
	}
	if(ans==INF) ans = -1;
	cout << ans << "\n";
}