U420877 【模板_A*第k短路】日期Remmarguts' Date

Remmarguts王子住在UDF王国里。有一天他们的邻国因为外交事务送来了他们的Uyuw公主。 在此之前，公主给Remmarguts寄了一封信，告诉他她会来宫殿参加商务会议，当且仅当王子能够通过第k短的道路来见她。对贸易发展和这样一个可爱的女孩都感兴趣，Remmarguts王子真的动心了。他需要你这个总理的帮助。 细节：UDF的首都有N个站点，宫殿标号为S，标号T的站点表示王子现在的位置。M条泥泞的有向道路连接了其中一些站点。Remmarguts去迎接公主的道路可能包含其中一些站点多次，即使这个站点的标号为S或者T。同一长度的不同路线视为不同。

第一行包含两个整数N和M(1

输出一行包含一个整数，迎接公主的第k短道路的长度。如果不存在第k短的道路，输出-1。