经过一顿计算，小A终于破开了魔法阵。
"小C，吓坏了吧，有没有哪里受伤了？都瘦了，有没有饿肚子？balabala~~~" 小A拉着小C的手不停的问道
"瞧你那样~~我没事啦，我就知道你一定能找到我~" 小C开心的说着
"啧啧啧，行了行了，别在本大仙面前秀恩爱了，本大仙只吃天鹅肉，不吃狗粮。你们还是想想怎么逃出去吧！"
"啊~~怪兽啊，好可怕啊！它还会说话！" 小C闻声看去，却发现是一只大蛤蟆，不由得尖叫到
"你怎么回事，见到英俊潇洒，风流倜傥的本大仙，你给我演这一出？ 信不信我揍你？？"
"不信" 小A看见小C受惊了，撸起袖子就要开干
"别打别打，惹不起你们，我还躲不起你们吗，从此以后，你们走你们的独木桥，我走我的阳光大道，我们互不相欠！
解决了最后一个问题，我们就各自分道扬镳吧！balabalabala~~~"
原来，这个世界有n个传送阵，这n个传送阵之间有m个传送通道，传送阵的编号从0到n-1，一个传送阵只能通过传送通道传送到其他传送阵。他们现在处在0号传送门阵上
而n-1号传送阵能够通往地球！蛤蟆小晋也想去n-1号传送阵，但是小A又不想让小C看见这个烦人的蛤蟆，所以小A不得不设计一个方法，
使得他们与蛤蟆小晋，不能通过相同的传送阵也不能通过相同的传送通道(除了起点0和终点n-1)，现在我们知道通过每个传送通道需要
花费的代价，请计算出一个方案使得小A小C与蛤蟆到达终点所花费的代价和最小，如果有一方无法到达终点则输出-1
数据过弱等待加强
有多组输入，请处理到EOF
每组数据第一行为两个整数n和m，代表传送阵的数目和传送通道的数目。(0<n<=1000,0<m<=10000)
接下来m行每行三个整数u,v,w代表边的起点，终点和花费，通道是单向的(单向边)。(0<=u,v<n,0<w<=10000)
(可能有重边)
如果不能满足题目要求输出-1，否则输出最短路径和。
2 1 0 1 20 2 2 0 1 20 0 1 20
-1 40