Một hãng tư nhân ở thành phố X vừa khánh thành một mê cung rất hấp dẫn khách tham quan. Mê cung có N phòng được đánh số từ 1 đến N và có M cầu thang, mỗi cầu thang nối trực tiếp hai phòng với nhau. Việc đi lại giữa các phòng chỉ có thể thực hiện thông qua các cầu thang. Phòng 1 là lối ra, vào duy nhất của mê cung. Các cầu thang không cắt nhau. Giữa hai phòng bất kỳ có không quá 1 cầu thang nối chúng. Không có cầu thang nối một phòng với chính nó. Thời gian đi mỗi chiều qua cầu thang là số được cho trước.
Nhân dịp khai trương mê cung, chủ hãng treo giải thưởng lớn cho du khách nào có cách thâm nhập vào mê cung và sau đó tìm cách ra ngoài với thời gian ít nhất. Tuyến đường phải bắt đầu từ phòng số 1, đi qua ít nhất một phòng (không kể phòng số 1) rồi quay lại phòng số 1 và thoả mãn yêu cầu: Mỗi cầu thang, mỗi phòng (không kể phòng số 1) đi không quá 1 lần.
Bạn Hoàng được dịp đi tham quan mê cung này, các bạn hãy giúp bạn Hoàng giành được giải thưởng theo yêu cầu trên.
Yêu cầu: Cho biết sơ đồ của mê cung, hãy tìm cách thâm nhập mê cung với thời gian ít nhất thoả mãn các điều kiện nêu trên.
Dữ liệu: Vào từ fle văn bản MECUNG.INP:
- Dòng thứ nhất chứa số nguyên N (3 ≤ N ≤ 5000) và M (3 ≤ M ≤ 10000);
- M dòng tiếp theo chứa thông tin về các cầu thang: Mỗi dòng chứa 4 số nguyên A, B, C, D được ghi cách nhau bởi dấu cách, cho biết phòng A và phòng B được nối với nhau bởi cầu thang, và theo cầu thang này: thời gian đi từ A đến B là C (phút) còn thời gian đi từ B đến A là D (phút), (1≤ C,D ≤10000)
Kết quả: Xuất ra màn hình thời gian ít nhất của bạn Hoàng khi thâm nhập vào mê cung.
Ví dụ:
| MECUNG.INP | Xuất ra màn hình |
| 4 51 2 1 101 3 5 12 3 1 92 4 10 203 4 60 70 | 3 |
Test 1 = 4
7 8
1 2 1 20
2 3 1 2
3 4 1 15
4 5 1 16
5 6 1 18
6 7 1 22
1 7 20 1
2 6 1 15
Test 2 = 5
4 5
1 2 2 40
1 3 50 1
2 3 2 60
3 4 2 50
1 4 60 2
Test 3 = 15
6 8
1 2 20 5
1 3 2 4
3 4 2 2
3 6 10 20
4 6 25 30
4 5 3 3
5 6 2 2
6 2 1 15
Test 4 = 10
10 45
1 2 232 242
1 3 286 993
1 4 1 472
1 5 386 210
1 6 1003 1
1 7 581 683
1 8 560 587
1 9 147 557
1 10 188 371
2 3 357 592
2 4 787 474
2 5 292 1
2 6 710 1016
2 7 2 272
2 8 933 126
2 9 106 312
2 10 692 174
3 4 1070 2
3 5 2 505
3 6 648 217
3 7 908 827
3 8 809 583
3 9 130 572
3 10 969 367
4 5 715 476
4 6 362 907
4 7 784 170
4 8 194 998
4 9 954 597
4 10 502 1087
5 6 423 815
5 7 619 571
5 8 329 505
5 9 378 1076
5 10 668 1017
6 7 550 1
6 8 965 329
6 9 859 158
6 10 1036 451
7 8 794 893
7 9 361 755
7 10 862 352
8 9 696 766
8 10 417 812
9 10 908 708