所以她通过记住 个路标来找到回不卜庐的路。
总共有 对直接相连且双向连通的路标，所有路标都是直接或间接连通的。
在七七的记忆中,第 对直接连接的路标的距离是
七七知道自己记忆力差，经常忘记路标与路标之间的距离，所以她在出发前总是会看看随身携带的璃月地图，地图上第 个直接连通的路标之间的距离 。
但是七七还知道，她看不太懂地图，老是会弄错地图上的距离。所以在回不卜庐的过程中会感到疑惑，而当七七感到疑惑的时候就会受到磨损。
假设七七现在到达一个新的节点 ，她会重新计算当前节点到不卜庐的最短路径。

她通过记忆中的路径长度计算出，此时走第 条路是返回不卜庐的最短路。
她通过地图中的路径长度计算出，此时走第 条路是返回不卜庐的最短路。

如果 ，那么不论七七选择走第 条路还是走第 条路，那么七七都会感到疑惑，并受到1点磨损。
如果 ，并且七七选择走第 条路那么七七就不会感到困惑，也就不会受到磨损。
如果最终七七既不选择走第 条路，也不走第 条路，那么无论 和 是否相等，七七都会感到双倍的疑惑，并且受到2点磨损。
现在，请你帮七七设计一条路径，让七七回到不卜庐时受到的磨损最小。

第一行两个整数 ，表示有  个路标，总共有  对路标直接相连。
七七现在在1号路标处，不卜庐就是号路标。
接下来  行，每行四个整数。
第  行有 四个数， 表示直接相连的两个路标， 表示七七记忆中的路径长度， 表示地图上的路径长度。

一个整数，表示七七受到的磨损。

5 7
3 5 8 9
1 3 1 2
3 4 3 2
1 4 5 3
4 5 3 4
4 2 3 2
2 5 3 2

1

在七七的记忆中，每条边的长度如下图所示

七七看到的地图上，每条边的长度如下图所示


当七七在1号点时：
用记忆中的路径长度计算，到达5号点的最短路径是1-3-4-5
用地图上的路径长度计算，到达5号点的最短路径是1-4-2-5
七七无论选择走哪条路都会受到1点磨损。

当七七在4号点时：
用记忆中的路径长度计算，到达5号点的最短路径是4-5
用地图上的路径长度计算，到达5号点的最短路径是4-5或者4-2-5
七七如果选择走4-5则不会受到磨损。
七七如果选择走4-2则会受到1点磨损（因为4-2这条边在七七的记忆中并不在到达5号点的最短路上）。

当七七在3号点时：
用记忆中的路径长度计算，到达5号点的最短路径是3-4-5
用地图上的路径长度计算，到达5号点的最短路径是3-4-5或者或3-4-2-5
如果七七选择走3-5则会受到2点磨损。
如果七七选择走3-4则不会受到磨损。

最终，七七可以选择走1-4-5或者1-3-4-5这两条路径从而达到磨损最小，总磨损为1。