TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.5% (19/21)

Submission's AC Ratio

21.7% (45/207)

Tags

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 1

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

Sample Output 1

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 (VSS, 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