1574: 糟糕的网络

前几天sqybi 还在高高兴兴的用BOINC 完成着一个又一个的任务呢，但现在sqybi 突然变得闷闷不乐起来。原因就是前一段时间的海底地震震断了光缆，导致了国外网站的整体瘫痪，而BOINC 的大部分工作的主站都是设在国外的。这样，sqybi 就不能从BOINC 下载到任务了，而他已经完成的任务也不能上传。

气愤的他打算自己找到在光缆断裂的时候最好的一条电缆替代线路。通过电流在电缆中传播的衰减公式（由汤姆逊博士发现），我们可以知道电缆之间的距离越远，那么电子衰

减的就越严重。所以，sqybi 想找到一条距离最短的电缆传输线路。

已知每一个电缆结点（就是说电缆数据在这个地方可以进行交换传输）的编号和它们之间的电缆分布情况，求出从0 结点指向n+1 结点最短的一条线路。

第1 行是一个正整数n，表示电缆结点的数量（不包括0 结点和n+1 结点）。

第2 行是一个正整数m，表示电缆的数量。

接下来m 行，第i 行表示第i-2 条电缆的四个数，分别是整数L、x1、x2 和s，每两个数之间用一个空格分开。其中L 表示该条电缆的长度；当s 为1 的时候，这条电缆是从x1 结点指向x2 结点的一条单向电缆，而当s 为2 的时候，这条电缆是在x1 结点和x2 结点之间的一条双向电缆。

仅一个数，为最短线路的长度。

3
4
1 0 1 1
1 1 2 2
1 2 3 1
2 3 4 1

5