Bear là môt nhà du thám (du lịch và thám hiểm) nổi tiếng với khả năng di chuyển và trải nghiệm trong những điều kiện vô cùng khắc nghiệt. Trong chuyến du thám sắp tới, anh sẽ đến với một vùng biển hẻo lánh của biển Nam Thái Bình Dương. Quần đảo này gồm ~N~ đảo (các đảo được đánh số thứ tự từ ~1~ đến ~N~). Việc di chuyển giữa ~N~ đảo này được đáp ứng bởi ~m~ chuyến phà (mỗi chuyến phà đáp ứng nhu cầu di chuyển đi lại giữa hai đảo cố định nào đó), đủ đảm bảo để từ mỗi đảo có thể đến được bất kỳ đảo khác bằng cách trực tiếp hoặc thông qua các tuyến phà trung gian.

Sau khi có được những thông tin cần thiết, Bear đặt ra nhiệm vụ như sau cho chuyến du thám: Chọn ra ~N-1~ trong số ~M~ tuyến phà để thực hiện hành trình đến ~N~ đảo, mỗi đảo ít nhất một lần, sao cho tổng thời gian thực hiện (đơn vị tính là phút) là nhỏ nhất. Bear sẽ đổ bộ xuống đảo ~1~, thực hiện hành trình, quay về đảo ~1~ rồi thoát khỏi máy bay để hoàn thành nhiệm vụ đặt ra. Hành trình có thể phải lặp lại nhiều hơn ~1~ lần đối với một số đảo cũng như tuyến phà.

Các thông tin mà Bear có được bao gồm:

• ~M~ tuyến phà với thời gian di chuyển tương ứng bởi tuyến đó;

• Thời gian mà Bear cần để thoát ra khỏi mỗi đảo kể từ lúc đặt chân đến.

Yêu cầu: Hãy tính xem trong chuyến du thám của mình, Bear có thể hoàn thành nhiệm vụ đặt ra với tổng thời gian nhỏ nhất là bao nhiêu?

Input

Cho trong file văn bản BEAR.INP có cấu trúc như sau:

• Dòng đầu tiên ghi hai số nguyên ~N~ và ~M~ ~(5 \le N \le 10000,\ N < M \le 100000)~;

• Dòng thứ ~2~ ghi ~N~ số nguyên ~S_1,\ S_2,\cdots ,\ S_N~ cho biết: ~S_i~ là số đơn vị thời gian tối thiểu để Bear thoát ra khỏi đảo ~i~ ~(1 \le S_i \le 1000;\ i=1,\ 2,\cdots ,N)~;

• Mỗi dòng trong ~M~ dòng tiếp theo ghi thông tin một tuyến phà bao gồm ~3~ số nguyên ~u,\ v~ và ~T~ ~(1\le u,\ v\le N,\ 1\le T\le 1000)~ với ý nghĩa: ~T~ là số đơn vị thời gian di chuyển theo tuyến phà giữa các đảo ~u~ và ~v~.

Lưu ý: nói riêng tại đảo ~1~, mỗi lần thâm nhập vào đảo này, Bear cũng đều cần thời gian tối thiểu ~S_1~ mới thoát ra khỏi nó.

Output

Ghi ra tệp văn bản BEAR.OUT duy nhất một số nguyên, là tổng thời gian nhỏ nhất mà Bear có thể cần để hoàn thành nhiệm vụ.

Scoring

~50\%~ số Test ứng với ~50\%~ số điểm của bài có ~N \le 1000~

Sample Input 1

6 10
5 2 7 4 5 8
1 3 5
2 3 6
3 1 4
2 4 7
5 6 3
4 5 8
2 6 6
5 3 5
2 5 9
3 4 4

Sample Output 1

105