TopCoder

Thumb rezero
Re Zero
Re Zero

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

23.5% (8/34)

Description

經過了一連串的冒險, 終於救出了妁艷, 摧毀了邪惡組織的陰謀.
這時, 冥王星上除了妁艷, 妤嬌, 姊姊, 妹妹, 火姬之外, 沒有任何人了.
“葛格, 我們走吧! 回地球去吧!” 妁艷妹妹說.
“恩.., 好不容易來到冥王星的, 這樣就回去實在太可惜了.” 妁艷說.
“不做嗎?” 妁艷繼續說.
“我才沒有...” 妁艷妹妹紅著臉頭偏向一邊說.

“其實妳很想要對吧!? 看看妳的表情!?” 妁艷接著說.
“葛格, 但是你的微甲..., 啊啊啊, 不要♥ ”
“嘴巴上說不要, 身體倒是挺誠實的嘛!” 妁艷強拉著妹妹的手.

想不到妁艷妹妹竟然有在冥王星上散步的興趣.

兩人決定在返回地球前, 在冥王星上逛一圈.
為了不讓其他人等太久, 他們決定以最快的速度參觀一些冥王星上的風景然後返回原地.
但是參觀重複的地方實在太無聊了, 他們決定不經過重複的地方或道路.

“啊, 好刺激, 再這樣下去的話我會~~~♥ ” 妁艷妹妹表示其對路上風景的看法.
“平時看起來很乖巧的, 在這種時候果然很變態呢!” 妁艷說.

冥王星上有許多景點, 包含原出發點. 同時, 有許多道路連接於景點之間, 兩景點最多有一條路連接.
一條道路可能是在坡道上, 所以兩個方向行進的時間可能不同.

為了不讓妁艷妹妹壞掉, 保證冥王星上存在一條路徑不經過重複的道路或景點, 並返回出發點.

Input Format

第一行有兩個正整數n, m, 代表有幾個景點幾條道路, 其中第1個景點為出發點.
接下來有m行, 每行有四個正整數a, b, c, d, 其中a ≠ b. 分別代表有條道路連接第a, b兩景點, 而從a到b要花c單位的時間, 從b到a要花d單位的時間.

對30%的測資n ≤ 50
對60%的測資n ≤ 3,000, m ≤ 5,000
對100%的測資n ≤ 5,000, m ≤ 10,000, 1 ≤ c, d ≤ 10,000

Output Format

輸出一個數字, 以最快的速度參觀冥王星上的一些風景然後返回原地需要多久.

Sample Input

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

Sample Output

6

Hints

Problem Source

原TIOJ1793 / problem setter: willyliu; source: POI XI The Competition

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536
7 2000 65536 65536
8 2000 65536 65536
9 2000 65536 65536