TopCoder

Thumb 1580873255888  1
Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

12.3% (14/114)

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10