Consider a weighted undirected graph G with n nodes numbered from 1 to n and m edges. Each node is associated with an alphabet and you can either jump between nodes with same letter (in 0 time) or to any node that is directly adjacent to a node. You are required to find out the shortest path between 1 and n(if it exists).

Constraints

1 <= n<= 100000

1 <= m <= 200000

1 <= weights <= 1000000

Input

First line contains two integers: n, m denoting number of nodes and edges respectively. Next m lines contains three integers each: u, v, w denoting there is an edge between u & v and w is the weight of that edge. It is followed by n lines each containing a lowercase alphabet associated with node i.

Output

A single integer denoting the shortest path between 1 and n if a path exists else -1.