Workman Ivan lost his job. Not because of truancy or being late, and not because the
plant where he had been working was left without orders. The reason for
dismissal was the stale aspic he had presented to his boss for his birthday.
After one more day of fruitless job search he dropped in a supermarket near his
home. He had a little money left, so he visited the liquor department. Waiting
in the line to the cashier's desk, he recognized the man buying a bottle of
expensive brandy. That was his old acquaintance Vassily. After loud greetings
and an argument about the best variety of brandy, they went out into the street at last.
“Well, how are you, my friend?” Vassily asked.
“Looking for a job,” Ivan answered wearily.
“You know, I was also looking for a job not so long ago, and I found an
excellent one!” Vassily was excited. “It's nearby and they
promised to pay well! And you can join us too!”
“What's that job like?” no wonder, jobless Ivan became interested.
“Have you heard about the company Ostap and Partners? They've
been producing horns and hoofs for a number of years already. And now I'm a
hoof picker of the third class with them!” answered Vassily proudly.
“How much do they pay you?” Ivan wanted to know.
“They don't pay me yet,” answered his friend with disappointment.
“It's the first month I work there and I'm a probationer. And the guys in the brigade
don't tell me their wages, it's the company's policy.” He paused and lowered his voice to a whisper.
“But I know that our foreman drives a Mercedes!”
“Ah, I would like to know how much money they get,” Ivan said dreamily
imagining himself driving a Merc.
“I can learn it after all!” Vassily had a sudden inspiration.
“The guys like to brag at smoking breaks that their wages are greater than
someone else's. For example, Stepan said recently that he was getting 1200
rubles more than Fyodor. And Fyodor once complained that he was getting
5500 rubles less than the foreman.”
“Collect then as many such comparisons as you can, and we will know all
the wages!” Ivan rejoiced.
“OK, I'll do that!”
In a week, Vassily brought a notebook with a number of records about the
comparisons of the workmen's wages. So they started calculations…
The first line contains the number n of the workmen in the brigade and
the number m of records in the notebook (1 ≤ n, m ≤ 50000).
Each of the following m lines contains three integers: i, j, and d,
which mean that the wage of the i-th workman is greater than the wage of the
j-th workman by d rubles
(0 ≤ i, j ≤ n−1; |d| ≤ 20000).
The workmen are enumerated from 0 to n−1 starting from Vassily,
whose wage is zero. It is known that no workman gets more than 109 rubles.
If it is possible to find amounts of wages that lie in the given range and
satisfy all the comparisons from the notebook, output
“Possible” in the first line and then output n integers
each in the separate line which are
the possible amounts in the ascending order of the workmen's numbers.
If several answers are possible, output any one of them.
If there is no answer, output the only line with the words
“Impossible after i statements”, where the number i
is the number of the first record in the notebook such that considering only the
preceding records it is possible to find an answer and with the addition of
this record it becomes impossible. The records are enumerated starting from the
number one in the order in which they are given.
3 4 1200
4 1 -5500
2 3 4300
3 0 8200
0 4 -7000
2 1 0
1 2 5
0 2 0
1 0 -5
1 2 5
2 2 0
Impossible after 3 statements
1 0 871
1 2 903
Impossible after 2 statements
Problem Author: Dmitry Ivankov
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009