Một người bạn của bạn làm nghề quản tượng được lệnh đưa voi tới cung điện. Các con đường tới cung điện đều thu phí và người quản tượng phải tự trả tiền. Hãy giúp người ấy tìm một hành trình có tổng phí nhỏ nhất.

Bản đồ gồm các trạm thu phí và các con đường. Cần tuân theo các quy tắc sau:

• Mỗi con đường là một đoạn thẳng nối hai trạm thu phí và có thể đi theo cả hai chiều. Giữa một cặp trạm có nhiều nhất một con đường.
• Phải đi hết một con đường từ đầu này tới đầu kia. Không được chuyển sang đường khác ở giữa đường, kể cả tại giao điểm của hai đường.
• Tại một trạm, voi không thể chuyển giữa hai đoạn đường tạo thành một góc nhọn. Cụ thể, khi đi từ \(p\) tới \(q\) rồi tới \(r\), góc \(\angle pqr\) giữa hai tia \(qp\) và \(qr\) phải lớn hơn hoặc bằng \(90^\circ\). Góc vuông và góc tù đều được phép.

Voi bắt đầu ở trạm \(1\). Cung điện nằm ngay cạnh trạm \(2\); mục tiêu là tới trạm \(2\).

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(n,m\): số trạm thu phí và số con đường.
• Dòng thứ \(i+1\) (\(1\le i\le n\)) chứa hai số nguyên \(x_i,y_i\), là tọa độ trạm \(i\).
• Dòng thứ \(j+n+1\) (\(1\le j\le m\)) chứa ba số nguyên \(a_j,b_j,c_j\), cho biết có một con đường nối trạm \(a_j\) với trạm \(b_j\), với phí đi qua là \(c_j\).

Các số trên cùng một dòng được phân cách bằng dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn tổng phí nhỏ nhất để đi từ trạm \(1\) tới trạm \(2\) theo các quy tắc trên. Nếu không thể tới được trạm \(2\), ghi -1.

Ràng buộc

• \(2\le n\le100\).
• \(-10\,000\le x_i,y_i\le10\,000\) (\(1\le i\le n\)).
• \(1\le a_j<b_j\le n\) (\(1\le j\le m\)).
• \(0\le c_j\le10\,000\) (\(1\le j\le m\)).
• Giữa một cặp trạm có nhiều nhất một con đường.

Phân nhóm

Các bộ dữ liệu được chấm độc lập; không có điều kiện ràng buộc riêng cho từng nhóm.

• Các bộ dữ liệu \(01\)–\(10\): \(10\) điểm mỗi bộ, tổng cộng \(100\) điểm; áp dụng toàn bộ ràng buộc trên.

Ví dụ

5 6
0 0
10 10
0 10
10 0
2 -6
1 2 30
1 3 4
1 4 5
1 5 1
2 4 3
2 5 1

8