ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Ostap and Partners

Time limit: 2.0 second
Memory limit: 64 MB
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…

Input

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, jn−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.

Output

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.

Samples

inputoutput
5 6
3 4 1200
4 1 -5500
2 3 4300
3 0 8200
0 4 -7000
2 1 0
Possible
0
12500
12500
8200
7000
3 5
1 2 5
0 2 0
1 0 -5
1 2 5
2 2 0
Impossible after 3 statements
3 2
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
To submit the solution for this problem go to the Problem set: 1701. Ostap and Partners