You have been given an undirected graph containing of N nodes and M edges. Each of the edges have a lowercase character('a'-'z') written on them. Hence, each path from 1 to N can be described with a string consisting of characters coming on the path. You have to find lexicographic K^th shortest path from 1 to N in this graph.

INPUT:
First Line of input consists of three integers N ,M and K. Next M lines consists of two integers u and v and a character c denoting an edge between u and v with label c .

OUTPUT:
Print lexicographical K^th shortest path in this graph from 1 to N. If total number of shortest paths are less than K, print -1.

CONSTRAINTS:
2 ≤ N ≤ 10⁵
N-1 ≤ M ≤ 10⁶
1 ≤ K ≤ 10¹⁸
1 ≤ u,v ≤ N
c will be a lower case alphabet ('a'-'z').
Graph will not contain self loops and parallel edges. 1 and N will lie in same connected components.