Description

你要参加一个机器人比赛。在正常的巡线机器人比赛中，机器人需要沿着黑色的线移动。而在高端的学术型机械比赛 ACM（Academic Competition of Machine）中，机器人需要沿着各种颜色的边移动。

你的比赛地图是一个 $n$ 个点 $m$ 条边的简单无向图。每条边都有一个颜色 $c_i$，颜色的范围为 $[1,m]$，但不保证所有边颜色两两不同。

你的机器人从点 $1$ 出发，目的地是点 $n$. 机器人只有唯一的移动方式：你指定一个颜色，满足连接这个点的边中（含走过的），有且仅有一条边的颜色是你指定的颜色，然后机器人沿着你指定的颜色的边移动到下一个点。

到达点 $n$ 这件事不一定总能实现，此时你需要贿赂比赛的主办方。在比赛进行的任意时刻，对于一条边 $i$，你都可以支付 $p_i$ 元贿赂主办方。若这么做，你可以将这条边的颜色修改为任意 $[1,m]$ 中的任意颜色。注意，即使一条边 $i$ 曾被修改过颜色，当你希望再次修改时，需要再次支付 $p_i$ 的费用。

你意识到你被骗了，高端的学术型机械比赛怎么会公然允许选手付费开挂呢？但无论如何，你都已经参加了，所以你只能希望在这场伪装成 ACM（Academic Competition of Machine）的 ACM（Awful Competition of Money）比赛中，支付尽量少的费用。

Format

Input

第一行输入两个正整数 $n,m\,(1\leq n\leq 10^5,1\leq m\leq 3\times10^5)$.

随后 $m$ 行，每行输入四个正整数 $u,v,c,p\,(1\leq u,v\leq n,1\leq c\leq m,1\leq p\leq 10^9)$，表示一条边连接的两个点、颜色和贿赂费用。

Output

若无解，仅输出一个数 $-1$.

否则输出一个数表示支付的最小费用。

Samples

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

3

先支付 $2$ 费用将第 $6$ 条边修改为颜色 $3$，然后沿颜色为 $3$ 的边移动，从点 $1$ 到达点 $2$.

再支付 $1$ 费用将第 $4$ 条边修改为颜色 $2$，然后沿颜色为 $2$ 的边移动，从点 $2$ 到达点 $4$.

总的费用 $1+2=3$.

Limitation

1s, 256MiB.

所有数据点属于一个 subtask.