Một lớp học có \(n\) học sinh, các học sinh được đánh số từ 1 đến \(n\). Thầy giáo chủ nhiệm muốn chọn ra một nhóm bạn để tham gia một trò chơi, một trò chơi cần sự phối hợp nhịp nhàng giữa các thành viên trong nhóm. Là một giáo viên nhiều kinh nghiệm, thầy giáo chủ nhiệm đã biết được sự phối hợp của \(m\) cặp học sinh, một cặp học sinh \(i(1 \leq i \leq n)\) và học sinh \(j(1 \leq j \leq n)\) có sự phối hợp là giá trị \(c(i, j)\), điều này có nghĩa là nếu học sinh \(i\) và học sinh \(j\) cùng được chọn vào nhóm thì tổng sự phối hợp của nhóm sẽ được cộng giá trị \(c(i, j)\), biết rằng \(-10^9 \leq c(i, j) \leq 10^9\).

Yêu cầu: Cho \(n\) học sinh và \(m\) cặp học sinh mà thầy giáo chủ nhiệm đã biết, hãy giúp thầy giáo chủ nhiệm chọn ra một nhóm để tổng sự phối hợp của nhóm là lớn nhất.

Input

• Dòng đầu tiên chứa các số nguyên \(n, m\).
• Dòng thứ \(k(1 \leq k \leq m)\) trong \(m\) dòng tiếp theo chứa 3 số nguyên \(i_k, j_k, c(i_k, j_k)\).

Output

• Dòng đầu tiên chứa số nguyên \(s\) là số học sinh trong nhóm.
• Dòng thứ hai gồm số \(s\) là chỉ số các bạn học sinh được chọn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 20\)
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 200\) và giá trị \(c(i, j)\) chỉ nhận một trong hai loại giá trị \(1\) hoặc \(-10^9\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 200\)

** Cách tính điểm **

Có \(20\) test, mỗi test \(5.0\) điểm. Với mỗi test, gọi tổng sự phối hợp của nhóm do thí sinh tìm được là \(c, q\), là tổng sự phối hợp của nhóm trong lời giải của Ban giám khảo, nếu \(c \leq 0\) thí sinh sẽ được \(0\) điểm, ngược lại số điểm của thí sinh đạt được là \(5.0 \cdot min\left(1, \dfrac{c^3}{q^3}\right)\)

Example

5 4
1 5 1
1 2 -1
2 5 3
1 4 -1 

3
1 2 5