Hôm nay, tỷ phú Christian đã học về thuật toán Dijkstra với các thế năng Johnson. Anh thích nó đến mức quyết định thêm thế năng vào tất cả đồ thị yêu thích của mình. Sở thích của Christian rất đặc biệt: anh chỉ giữ các đồ thị có hướng có trọng số trong căn phòng bí mật.

Hãy nhắc lại cách thế năng hoạt động. Mỗi đỉnh $v$ được gán một thế năng: số thực $\varphi(v)$. Nếu trước đó có một cạnh từ $u$ đến $v$ có trọng số ban đầu $w$, trọng số mới của cạnh sẽ là $w'=w-\varphi(v)+\varphi(u)$.

Sức mạnh của một đồ thị được định nghĩa là giá trị nhỏ nhất trong các trọng số cạnh của nó. Christian không muốn những đồ thị yếu trong phòng mình, nên anh muốn chọn các thế năng sao cho sức mạnh của đồ thị lớn nhất. Hãy giúp anh.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ ($2\le n\le1000$) và $m$ ($1\le m\le100\,000$), là số đỉnh và số cạnh trong đồ thị yêu thích của Christian. Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $u_i,v_i,w_i$ mô tả một cạnh: lần lượt là đỉnh đầu, đỉnh cuối và trọng số ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).

Dữ liệu ra

Dòng đầu phải chứa sức mạnh lớn nhất của đồ thị. Nếu có thể làm đáp án lớn vô hạn, thay vào đó in chuỗi “+inf”.

Nếu đáp án hữu hạn, dòng thứ hai phải chứa $n$ số thực: thế năng của các đỉnh. Giá trị tuyệt đối của mỗi số không được vượt quá $10^{10}$. Đáp án của bạn phải sai khác không quá $10^{-5}$ so với cả đáp án đúng lẫn đáp án tính từ các thế năng mà bạn đưa ra.

Ví dụ

Dữ liệu vào 1

3 3
1 2 1
2 3 1
3 1 1

Dữ liệu ra 1

1.0
0.0 0.0 0.0

Dữ liệu vào 2

2 1
1 2 1

Dữ liệu ra 2

+inf