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 Kth 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 Kth shortest path in this graph from 1 to N. If total number of shortest paths are less than K, print -1.
CONSTRAINTS:
2 ≤ N ≤ 105
N-1 ≤ M ≤ 106
1 ≤ K ≤ 1018
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.
All the 4 path strings from 1 to 7 are aaab, aaab, aaac and aaac. Lexicographic 4th one will be aaac.
