Trường trung học JOI mà bạn theo học tổ chức một cuộc thi định hướng mỗi năm một lần, với sự tham gia của toàn bộ học sinh. Thi định hướng là môn thi trong đó người tham gia dùng bản đồ và la bàn để đi qua các điểm kiểm tra được bố trí trên địa hình đồi núi.

Đặc điểm của cuộc thi ở trường JOI là học sinh tham gia theo đội hai người. Hai người trong mỗi đội cùng xuất phát từ điểm xuất phát được chỉ định, sau đó có thể di chuyển riêng để đến đích. Khi cả hai đã đến đích, mỗi điểm kiểm tra phải được ít nhất một người trong đội ghé qua. Hai người được phép ghé cùng một địa điểm và đi cùng một con đường trên hành trình.

Cuộc thi diễn ra trên núi JOI, nơi có \(N\) địa điểm và \(M\) con đường nối các địa điểm. Các địa điểm được đánh số từ \(1\) đến \(N\). Điểm xuất phát là địa điểm \(1\) ở chân núi, còn đích là địa điểm \(N\) trên đỉnh núi. Một số hoặc tất cả các địa điểm ngoài điểm xuất phát và đích được chọn làm điểm kiểm tra.

Để tránh hỗn loạn, trong thời gian thi, mỗi con đường chỉ được đi theo một chiều từ địa điểm thấp hơn đến địa điểm cao hơn. Không có hai địa điểm nào có cùng độ cao. Địa điểm \(1\) có độ cao thấp nhất và địa điểm \(N\) có độ cao cao nhất, nhưng số hiệu các địa điểm không nhất thiết được sắp theo thứ tự độ cao tăng dần. Ngay cả khi các đường được quy định một chiều như trên, từ địa điểm \(1\) vẫn có thể đến mọi địa điểm và từ mọi địa điểm vẫn có thể đến địa điểm \(N\).

Yêu cầu

Tìm tổng quãng đường nhỏ nhất mà hai người trong một đội phải đi để thỏa mãn các điều kiện. Dữ liệu bảo đảm tồn tại cách di chuyển hợp lệ cho hai người.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi một dấu cách: số địa điểm và số con đường.
• \(N\) dòng tiếp theo cho biết những địa điểm nào là điểm kiểm tra. Dòng thứ \(i+1\) \((1\le i\le N)\) chứa số nguyên \(S_i\) bằng \(0\) hoặc \(1\). Nếu \(S_i=0\), địa điểm \(i\) không phải điểm kiểm tra; nếu \(S_i=1\), địa điểm \(i\) là điểm kiểm tra. Luôn có \(S_1=S_N=0\).
• \(M\) dòng tiếp theo mô tả các con đường. Dòng thứ \(j+N+1\) \((1\le j\le M)\) chứa ba số nguyên \(A_j,B_j,C_j\), cách nhau bởi dấu cách. Đường thứ \(j\) đi một chiều từ địa điểm \(A_j\) đến địa điểm \(B_j\) và có độ dài \(C_j\). Địa điểm \(A_j\) thấp hơn địa điểm \(B_j\). Luôn có \(A_j\ne B_j\), và không tồn tại đường \(k\ne j\) sao cho đồng thời \(A_k=A_j\) và \(B_k=B_j\).

Dữ liệu ra

In ra tổng quãng đường nhỏ nhất của hai người trong một đội khi di chuyển thỏa mãn các điều kiện.

Ràng buộc

• \(3\le N\le1\,000\).
• \(2\le M\le10\,000\).
• \(1\le K\le N-2\), trong đó \(K=S_1+S_2+\cdots+S_N\) là số điểm kiểm tra.
• \(1\le C_j\le10\,000\) với mọi \(1\le j\le M\).
• \(1\le A_j,B_j\le N\) và \(A_j\ne B_j\).
• \(S_i\in\{0,1\}\) và \(S_1=S_N=0\).
• Các địa điểm có độ cao đôi một khác nhau; mọi con đường đi từ thấp lên cao. Từ \(1\) có thể đến mọi địa điểm và từ mọi địa điểm có thể đến \(N\). Tồn tại một cặp hành trình từ \(1\) đến \(N\) đi qua tất cả điểm kiểm tra.

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(1\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các tỷ lệ dưới đây mô tả các tập dữ liệu có phần giao nhau:

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(K\le10\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn đồng thời \(N\le100\) và \(M\le500\).
• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn đồng thời \(K\le10\), \(N\le100\) và \(M\le500\).
• Các bộ dữ liệu chiếm \(50\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: \(K\le10\); hoặc đồng thời \(N\le100\) và \(M\le500\).

Ví dụ

8 12
0
1
0
0
1
1
0
0
1 4 5
1 6 5
4 2 4
4 7 9
4 5 6
2 5 8
2 8 3
6 2 7
6 7 8
7 3 2
3 5 7
5 8 3

29