I. Dormitory Mapping
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alexey, a first-year student, has settled into his new surroundings at the National University of Berland. He attends classes in the mornings and spends his evenings relaxing by playing video games or browsing social media. However, when he runs out of games and his internet access is cut off, he seeks new challenges.

One day, Alexey found a map of the university's dormitories, which consists of $$$n$$$ dormitories numbered from $$$1$$$ to $$$n$$$, connected by bidirectional roads. The roads allow students to easily visit one another, ensuring that there is a path between any pair of dormitories.

In an effort to practice his arithmetic skills, Alexey wrote the sum of the dormitory numbers connected by each road on the map and then set it aside.

Upon revisiting the map, Alexey discovered that the dormitory numbers have faded, but the sums written on the roads are still legible. He has assigned new numbers to the dormitories, labeled from $$$1$$$ to $$$n$$$. However, he soon realized that navigating the campus based on the new numbering could lead to confusion, especially when trying to find the dormitory of a third-year student who is celebrating a birthday.

To avoid getting lost, Alexey has asked for your help in recovering the original dormitory numbers. Given the sums on the roads and the new numbering, he hopes to restore the original identifiers before the exams.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 3 \cdot 10^5$$$) — the number of dormitories and the number of roads connecting them, respectively. The following $$$m$$$ lines provide the details of the roads in the format $$$a$$$ $$$b$$$ $$$s$$$ ($$$1 \leq a, b \leq n, 1 \leq s \leq 2\cdot n$$$) — where $$$a$$$ and $$$b$$$ are the new numbers of the road endpoints and $$$s$$$ is the sum inscribed on that road. No road connects a dormitory with itself. There are at most one road between two dormitories.

Output

In the first line, output $$$k$$$ — the number of valid ways to restore the original dormitory numbers. If $$$k \gt 0$$$, output any one valid permutation of numbers from $$$1$$$ to $$$n$$$ on the second line, where the $$$i$$$-th number indicates the original dormitory number corresponding to the new number $$$i$$$. Note that Alexey may have made errors when calculating the sums, and it might not always be possible to restore the original numbers.

Examples
Input
3 2
2 1 3
3 1 4
Output
1
1 2 3
Input
2 1
1 2 3
Output
2
1 2