Một lớp học có \(n\) học sinh, các học sinh được đánh số từ \(0\) đến \(n-1\). Thầy giáo chủ nhiệm muốn chọn ra một nhóm học sinh để tham gia một trò chơi. Việc chọn nhóm được đánh giá thông qua các tiêu chí như: học sinh thứ \(i\) có nên chọn hay không, hay có nên chọn hai học sinh \(i,j\) cùng với nhau hay không. Do đó, thầy giáo đã xây dựng một ma trận \(Q\) để đánh giá việc chọn một nhóm.

Cụ thể, ma trận \(Q = (q_{ij})\) là ma trận đối xứng kích thước \(n \times n\), các hàng được đánh số từ \(0\) đến \(n-1\), các cột được đánh số từ \(0\) đến \(n-1\). Một cách chọn tương ứng với một vector nhị phân \(x\) gồm \(n\) thành phần, \(x = (x_0, x_1, ..., x_{n-1})\) với ý nghĩa \(x_i = 1\) hoặc \(0\) tương ứng học sinh thứ \(i\) được chọn hoặc không chọn. Một cách chọn nhóm được gọi là tốt nếu hàm \(f(x)\) đạt giá trị càng lớn nhất càng tốt:

Yêu cầu: Hãy giúp thầy giáo chọn nhóm để hàm \(f(x)\) đạt giá trị càng lớn càng tốt.

Input

• Dòng đầu chứa hai số nguyên \(n\), \(m\), trong đó \(n\) là kích thước ma trận \(Q\), \(m\) là số phần tử của ma trận \(Q\) có giá trị khác \(0\) (\(n \leq 500\))
• \(m\) dòng sau, mỗi dòng chứa ba số nguyên \(i\), \(j\), \(q_{ij}\) (\(|q_{ij}| \leq 10^9\) với \(0 \leq i,j \leq n-1\))
• Dữ liệu đảm bảo \(f(x)\) tối ưu luôn dương.

Output

• Gồm một dòng chứa \(n\) số nguyên mô tả chọn nhóm.

Example

2 2
0 0 5
1 1 -5

1 0

Scoring

Gọi \(GV\) là giá trị hàm \(f(x)\) tối ưu, \(HS\) là giá trị hàm \(f(x)\) cho cách chọn nhóm của bạn, gọi \(S\) là điểm cho một test, khi đó điểm của bạn được tính như sau:

• Nếu \(GV \leq HS\) đạt \(S\) điểm
• Nếu \(0 < \frac{GV-HS}{GV} < 1\%\) đạt \((1-\frac{GV-HS}{GV}) \times \frac{3S}{4}\) điểm
• Nếu \(1\% < \frac{GV-HS}{GV} < 10\%\) đạt \((1-\frac{GV-HS}{GV}) \times \frac{S}{3}\) điểm
• Trường hợp còn lại đạt \(0\) điểm