暂无测试数据。

背景

NOI2014

描述

为了得到书法大家的真传,小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 𝑛 个节点 𝑚 条边的无向图,节点标号为
1,2,3, ... , 𝑛,边标号为 1,2,3, ... , 𝑚。初始时小 E 同学在 1 号节点,隐士则住在 𝑛 号节点。小 E 需要通过这一片魔法森林,才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪 就会对其发起攻击。幸运的是,在 1 号节点住着两种守护精灵:A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量,达到自己的目的。
只要小 E 带上足够多的守护精灵,妖怪们就不会发起攻击了。具体来说,无 向图中的每一条边 𝑒𝑖 包含两个权值 𝑎𝑖 与 𝑏𝑖 。若身上携带的 A 型守护精灵个数不 少于 𝑎𝑖 ,且 B 型守护精灵个数不少于 𝑏𝑖 ,这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击,他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事,小 E 想要知道,要能够成功拜访到 隐士,最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。

格式

输入格式

输入的第 1 行包含两个整数 𝑛, 𝑚,表示无向图共有 𝑛 个节点,𝑚 条边。
接下来𝑚行,第𝑖+1行包含 4 个正整数𝑋𝑖,𝑌𝑖,𝑎𝑖,𝑏𝑖,描述第𝑖条无向边。 其中 𝑋𝑖 与 𝑌𝑖 为该边两个端点的标号, 𝑎𝑖 与 𝑏𝑖 的含义如题所述。
注意数据中可能包含重边与自环。

输出格式

输出一行一个整数:如果小 E 可以成功拜访到隐士,输出小 E 最少需要携 带的守护精灵的总个数;如果无论如何小 E 都无法拜访到隐士,输出“-1”(不 含引号)。

样例1

输入

4 5
1 2 19 1 
2 3 8 12 
2 4 12 15 
1 3 17 8 
3 4 1 17

输出

32

样例2

输入

3 1
1 2 1 1

输出

--1

限制

2 ≤ 𝑛 ≤ 50,000
0 ≤ 𝑚 ≤ 100,000
1≤𝑎𝑖,𝑏𝑖 ≤50,000